280. Wiggle Sort

Given an unsorted arraynums, reorder itin-placesuch thatnums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, givennums = [3, 5, 2, 1, 6, 4], one possible answer is[1, 6, 2, 5, 3, 4].

S1： sort O(nlogn)

排序后，交换所有奇数位和它后一位

S2：greedy O(n)

当i是奇数且比前一个数小，或i是偶数且比前一个数大时，swap(nums[i], nums[i - 1])

证明：假设[0 ~i-1]已经wiggle sort

• 当i为奇数时， nums[i-1]<nums[i-2], 若nums[i] > nums[i-1],满足条件，否则nums[i]<nums[i-1]交换i，i-1后仍满足nums[i-1] < nums[i-2]
• 当i为偶数时，nums[i-1]>nums[i-1], 若nums[i] < nums[i-1],满足条件，否则nums[i]>nums[i-1]交换i，i-1后仍满足nums[i-1] > nums[i-2]

    void wiggleSort(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            if ((i & 1 && nums[i] < nums[i - 1]) || (!(i & 1) && nums[i] > nums[i - 1]) {
                swap(nums[i], nums[i - 1]);
            }
        }
    }

324. Wiggle Sort II

Given an unsorted arraynums, reorder it such thatnums[0] < nums[1] > nums[2] < nums[3]....

Example:
(1) Givennums = [1, 5, 1, 1, 6, 4], one possible answer is[1, 4, 1, 5, 1, 6].
(2) Givennums = [1, 3, 2, 2, 3, 1], one possible answer is[2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

S1: sort O(nlogn）

S2：index map O(n)

1. 找到中间元素 nth_element O(n) best， O(n^n) worst
2. 将数组分为三部分: 大于中间元素，等于中间元素, 小于中间元素 （用color sort的方法）

将大于中间元素的部分分配给从头开始依次增加的奇数idx, 将小于中间元素的分配给从尾部开始依次减小的偶数idx，

用(i * 2 + 1) % (n / 2) 实现这种分配。利用index map将分配的步骤和步骤2结合

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        n = nums.size();
        auto midptr = next(nums.begin(), n / 2);
        nth_element(nums.begin(), midptr, nums.end());
        int mid = *midptr;

        int left = 0, cur = 0, right = n - 1;
        while (cur <= right) {
            int idx = getIdx(cur);  //get actual idx
            if (nums[idx] > mid) {  //swap to left part
                int idxLeft = getIdx(left);
                swap(nums[idx], nums[idxLeft]);
                left++;
                mid++;  //避免死循环
            } else if (nums[idx] < mid) {  //swap to right part
                int idxRight = getIdx(right);
                swap(nums[idx], nums[idxRight]);
                right--;
            } else {  //mid part, left it as it is
                cur++;
            }
        }

    }

    private:
    int n;
    int getIdx(int i) {
        return (2 * i + 1) % (n | 1); //得到下一个比n小的奇数（由小到大） 或者 下一个比n小的偶数（由大到小）
    }
};