เราได้รับอาเรย์ Arr1[] และ Arr2[] ความยาวเท่าหรือต่างกัน Arr1[] เรียงจากน้อยไปมาก แต่มี 1 ตัววางผิดที่ ต้องหาตัวเลขจาก Arr2[] ที่สามารถแทนที่ตัวผิดที่ใน Arr1[] ทำให้ 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[] เรียงน้อยไปมากยกเว้น 1 ตัว
- ฟังก์ชัน sortMax(int arr1[], int arr2[], int n1, int n2) อัปเดต arr1[] หากพบตัวใน arr2[] ที่มากที่สุดและแทนที่ตัวผิดได้
- wpos เก็บ index ตัวผิด เริ่มต้น -1
- maxx เก็บค่าสูงสุดใน arr2[] ที่แทนที่ได้ เริ่มต้น -1
- ลูปหาตัวผิดใน arr1[] ถ้า arr[i] < arr[i-1] เก็บ wpos = i
- ลูป arr2[] หาตัวที่อยู่ระหว่าง arr1[wpos-1] และ arr1[wpos+1] เปรียบเทียบกับ maxx อัปเดต
- แทนที่ arr1[wpos] = maxx
- คืนค่า maxx ถ้าพบ มิฉะนั้น -1
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int sortMax(int arr1[], int arr2[], int n1, int n2) {
int wpos = -1;
int maxx = -1;
for (int i = 0; i < n1; i++)
if (arr1[i] < arr1[i-1])
wpos = i;
for (int 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] << " ";
}
return 0;
}
ผลลัพธ์
Maximum in arr2[] to make arr1[] sorted: 9 Arr1[]: 1 3 7 9 10 Arr2[]: 2 1 6 8 9
