Wiggle Sort II ใน C++

Wiggle Sort II

จัดเรียงอาร์เรย์ไม่เรียบลับ ให้เป็นรูปแบบ nums[0] < nums[1] > nums[2] < nums[3] ... (สลับน้อย-มาก)

ตัวอย่าง: [1,5,1,1,6,4] → [1,4,1,5,1,6] (หรือคำตอบที่ถูกต้องอื่นๆ)

ขั้นตอนการแก้ปัญหา (Virtual Indexing + nth_element)

คัดลอกอาร์เรย์เป็น x แล้วเรียงลำดับ
กำหนด i = n-1 (ชี้ค่ามากสุด), j = (n-1)/2 (ชี้ค่ากลาง)
เติมตำแหน่งคู่ (0,2,4...) ด้วยค่าจาก x[j] ลงมา (j--)
เติมตำแหน่งคี่ (1,3,5...) ด้วยค่าจาก x[i] ลงมา (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, j = (n - 1) / 2;
        for (int k = 0; k < n; k += 2) nums[k] = x[j--];
        for (int k = 1; k < n; k += 2) nums[k] = x[i--];
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [1,5,1,1,6,4]

Output: [1,6,1,5,1,4] (คำตอบที่ถูกต้องอาจหลายแบบ)