Wiggle Sort - Sắp xếp dao động (nums[0] <= nums[1] >= nums[2]...)

Cho mảng chưa sắp xếp, sắp xếp tại chỗ sao cho nums[0] <= nums[1] >= nums[2] <= nums[3]....

Ví dụ: [3,5,2,1,6,4] → [3,5,1,6,2,4] (có thể có đáp án khác).

Giải thuật (Greedy một lần duyệt)

Duyệt i từ 0 đến n-2. Nếu i chẵn mà nums[i] > nums[i+1] hoặc i lẻ mà nums[i] < nums[i+1] thì hoán đổi. Điều này đảm bảo tính chất wiggle tại vị trí i.

Cài đặt C++

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            if ((i % 2 == 0) == (nums[i] > nums[i+1]))
                swap(nums[i], nums[i+1]);
        }
    }
};

int main() {
    vector<int> v = {3,5,2,1,6,4};
    Solution ob;
    ob.wiggleSort(v);
    print_vector(v);
    return 0;
}

Đầu vào

{3,5,2,1,6,4}

Đầu ra

[3, 5, 1, 6, 2, 4, ]