C++ में विगल सॉर्ट II

मान लीजिए हमारे पास एक अनसॉर्टेड सरणी nums है। हमें इसे पुनर्व्यवस्थित करना है ताकि nums[0] < nums[1] > nums[2] < nums[3]... पैटर्न बने।

उदाहरण: [1,5,1,1,6,4] → [1,4,1,5,1,6] (या कोई वैध विगल क्रम)।

सॉर्ट + दो-पॉइंटर प्लेसमेंट

1. nums की कॉपी x बनाएँ और सॉर्ट करें।
2. i = n-1 (सबसे बड़ा), j = (n-1)/2 (मध्य)।
3. सम इंडेक्स (0, 2, 4...) पर छोटे आधे तत्व रखें: nums[l] = x[j--]।
4. विषम इंडेक्स (1, 3, 5...) पर बड़े आधे तत्व रखें: nums[l] = x[i--]।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> x(nums);
        sort(x.begin(), x.end());
        int n = nums.size();
        int i = n - 1;
        int j = (n - 1) / 2;
        
        for (int l = 0; l < n; l += 2) {
            nums[l] = x[j--];
        }
        for (int l = 1; l < n; l += 2) {
            nums[l] = x[i--];
        }
    }
};

int main() {
    vector<int> v = {1,5,1,1,6,4};
    Solution ob;
    ob.wiggleSort(v);
    for (int x : v) cout << x << " "; // 1 6 1 5 1 4 (वैध विगल)
    return 0;
}

इनपुट

[1,5,1,1,6,4]

आउटपुट

[1, 6, 1, 5, 1, 4, ]