Given an array of numbers A[N], how do we arrange them in the following order.
A[0] <= A[1] >= A[2] <= A[3]...A[N-1]
For example consider the array A =[6, 9, 36, 24, 42]
The answer can be [6, 36, 9, 42, 24]
. There can be multiple answers also like [6, 42, 9, 36, 24]
. We have to find out one such answer.
We can solve this problem in a simpler way by sorting the array first. Considering the same example as above
Sorted(A) = [6, 9, 24, 36, 42]
Method1: Start from the second element and swap the elements in pairs
6, 9<-> 24, 36<-> 42 ===> 6, 24, 9, 42, 36
Method2: Interleave the elements of the second half into the first half in reverse order
It becomes 6, 42, 9, 36, 24
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
using namespace std; | |
int main() { | |
int t; | |
cin >> t; | |
while( t-- ) | |
{ | |
int n,i; | |
cin >> n; | |
vector<int> nums(n); | |
for( i = 0; i < n; i++ ) | |
{ | |
cin >> nums[i]; | |
} | |
sort(nums.begin(), nums.end()); | |
for( i = 1; i < n-1; i += 2) | |
{ | |
swap(nums[i], nums[i+1]); | |
} | |
for( i = 0; i < n; i++ ) | |
cout << nums[i] << " "; | |
cout << endl; | |
} | |
return 0; | |
} |