Chúng tôi được cung cấp một mảng đã được sắp xếp. Chúng ta cần sắp xếp mảng này ở dạng tối đa, tối thiểu, tức là phần tử đầu tiên là phần tử tối đa, phần tử thứ hai là phần tử tối thiểu, phần tử thứ ba là phần tử tối đa thứ 2, phần tử thứ 4 là phần tử tối thiểu thứ 2, v.v. ví dụ -
Input : arr[ ] = { 10, 20, 30, 40, 50, 60 }
Output : { 60, 10, 50, 20, 40, 30 }
Explanation : array is rearranged in the form { 1st max, 1st min, 2nd max, 2nd min, 3rd max, 3rd min }
Input : arr [ ] = { 15, 17, 19, 23, 36, 67, 69 }
Output : { 69, 15, 67, 17, 36, 19, 23 } Có một cách tiếp cận duy nhất để sắp xếp lại một mảng ở dạng tối đa và tối thiểu -
Phương pháp tiếp cận để tìm ra giải pháp
Có một cách tiếp cận duy nhất để sắp xếp lại một mảng ở dạng tối đa và tối thiểu -
Phương pháp tiếp cận hai con trỏ
Sử dụng hai biến, min và max, ở đây sẽ trỏ đến phần tử tối đa và tối thiểu, đồng thời tạo một mảng trống mới có cùng kích thước để lưu trữ mảng được sắp xếp lại. Bây giờ, hãy lặp lại trên mảng và nếu phần tử lặp ở chỉ số chẵn, thì hãy thêm phần tử arr [max] vào mảng trống và giảm tối đa 1. nếu phần tử ở chỉ số lẻ, thì hãy thêm phần tử arr [min] vào mảng trống và tăng min lên 1. Làm điều này cho đến khi giá trị max nhỏ hơn min.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main () {
int arr[] = { 1, 2, 3, 4, 5, 6 };
int n = sizeof (arr) / sizeof (arr[0]);
// creating a new array to store the rearranged array.
int final[n];
// pointing variables to initial and final element index.
int min = 0, max = n - 1;
int count = 0;
// iterating over the array until max is less than or equals to max.
for (int i = 0; min <= max; i++) {
// if count is even then store max index element
if (count % 2 == 0) {
final[i] = arr[max];
max--;
}
// store min index element
else {
final[i] = arr[min];
min++;
}
count++;
}
// printing the final rearranged array.
for (int i = 0; i < n; i++)
cout << final[ i ] << " ";
return 0;
} Đầu ra
6 1 5 2 4 3
Giải thích về Quy tắc trên
- Các biến được khởi tạo là min =0 và max =array_length (n) - 1.
- for (int i =0; min <=max; i ++) để lặp qua mảng cho đến khi giá trị max lớn hơn min.
- Nếu số đếm là số lẻ, thì (tối đa) phần tử sẽ được thêm vào mảng cuối cùng và biến max sẽ giảm đi 1.
- Giả sử khi đó số đếm là chẵn (tối thiểu). Trong trường hợp đó, phần tử được thêm vào mảng cuối cùng và biến min được tăng thêm 1.
- Cuối cùng, mảng kết quả được lưu trữ trong mảng [] cuối cùng.
Kết luận
Trong bài viết này, chúng tôi đã thảo luận về giải pháp sắp xếp lại mảng đã cho về dạng max-min. Chúng tôi đã thảo luận về cách tiếp cận cho giải pháp và giải quyết nó bằng một giải pháp lạc quan với độ phức tạp về thời gian là O (n). Chúng tôi cũng viết một chương trình C ++ tương tự. Tương tự, chúng ta có thể viết chương trình này bằng bất kỳ ngôn ngữ nào khác như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.