Sắp xếp Wiggle II trong C++

Cho mảng nums chưa sắp xếp, sắp xếp lại sao cho nums[0] < nums[1] > nums[2] < nums[3].... Ví dụ: [1,5,1,1,6,4] → [1,4,1,5,1,6].

Giải thuật

• Tạo mảng x sao chép nums, sắp xếp x.
• i := x.size()-1, j := (x.size()-1)/2, n := nums.size().
• Với l từ 0 đến n-1, bước nhảy 2: nums[l] = x[j--].
• Với l từ 1 đến n-1, bước nhảy 2: nums[l] = x[i--].

Ví dụ mã 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 i = x.size() - 1;
        int j = (x.size() - 1) / 2;
        int n = nums.size();
        for (int l = 0; l < n; l += 2) nums[l] = x[j--];
        for (int l = 1; l < n; l += 2) nums[l] = x[i--];
    }
};

Đầu vào

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

Đầu ra

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