資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中能夠使另一個數組排序的陣列中的最大值
給定一個數字陣列Arr1[]和另一個數組Arr2[]，它們的長度相同或不同。Arr1[]中的元素按升序排列，只有一個元素未排序。我們必須從第二個陣列Arr2[]中找到一個元素，該元素可以替換Arr1[]中放置錯誤的元素，並使其排序。此外，如果有多個選項可用，則從Arr2[]中選擇的元素應為最大值。
輸入
Arr1[]= { 1,3,5,7,2,11 }, Arr2[]= { 4,8,7,10,9 }輸出
Maximum element that can make Arr1 sorted: 10
說明 − Arr2[]中可以使Arr1[]排序的數字 − 8、9、10，因為它們都>=7且<=11。其中10最大。
新的Arr1[]變為{1,3,5,7,10,11}，並且已排序。
輸入
Arr1[]= { 12,5,22,17 }, Arr2[]= { 4,8,7,10,9 }輸出
No such element.
說明 − Arr2[]中沒有數字>=12且<=22。
Arr1[]無法排序。
下面程式中使用的演算法如下
陣列arr1[]和arr2[]用於儲存數字。Arr1[]按升序排序，只有一個元素除外。
函式sortMax(int arr1[], int arr2[], int n1, int n2)接收兩個陣列及其長度，如果找到arr2[]中的元素是最大值並且可以替換arr[]中不正確的元素，則更新arr1[]。
將arr1[]中放置錯誤的元素的索引儲存在變數wpos中，初始值為-1。
maxx用於儲存arr2[]中那些可以替換arr1[]中放置錯誤的元素並使其排序的元素中的最大值。
首先遍歷arr1[]並找到不正確的元素。如果arr[i]
現在遍歷arr2[]並找到可以放在arr1[wpos-1]和arr[wpos+1]之間的元素。如果存在這樣的元素，則將其與maxx這樣的元素進行比較。
更新最大值。
最後用maxx替換arr1[wpos]。
如果找到這樣的元素，則返回maxx，否則返回-1。
如果沒有找到元素，則顯示一條訊息。
否則列印排序後的arr1[]。
示例
// C++ program to make array sorted
#include <bits/stdc++.h>
using namespace std;
int sortMax(int arr1[], int arr2[], int n1, int n2) //making arr1 sorted{
int wpos=-1;
int maxx=-1;
int i,j;
for(i=0;i<n1;i++)
if(arr1[i]<arr1[i-1])
wpos=i;
for(j=0;j<n2;j++){
if(arr2[j]>=arr1[wpos-1] && arr2[j]<=arr1[wpos+1])
if(arr2[j]>=maxx)
maxx=arr2[j];
}
if(maxx!=-1)
arr1[wpos]=maxx;
return maxx;
}
int main(){
int arr1[] = { 1, 3, 7, 4, 10 };
int arr2[] = { 2, 1, 6, 8, 9 };
int len1 = sizeof(arr1) / sizeof(arr1[0]);
int len2 = sizeof(arr2) / sizeof(arr2[0]);
int res=sortMax(arr1, arr2, len1, len2);
if(res==-1)
cout<<"No swap possible! No such element!";
else{
cout<<"Maximum in arr2[] to make arr1[] sorted:"<<res;
cout<<endl<<"Arr1[]:";
for(int i=0;i<len1;i++)
cout<<arr1[i]<<" ";
cout<<endl<<"Arr2[]:";
for(int i=0;i<len2;i++)
cout<<arr2[i]<<" ";
}
}輸出
Maximum in arr2[] to make arr1[] sorted:9 Arr1[]:1 3 7 9 10 Arr2[]:2 1 6 8 9
更新於：2020年8月3日
100 次檢視
廣告