280. Wiggle Sort - cocoder39/coco39_LC GitHub Wiki

280. Wiggle Sort

The rule is: if i is odd, nums[i] >= nums[i - 1]; if i is even, nums[i] <= nums[i - 1]

Suppose elements from index 0 to i - 1 is already wiggle sorted. if i is even, then i - 1 is odd and nums[i - 1] >= nums[i - 2]. if nums[i] > nums[i - 1], then nums[i] > nums[i - 2], swap(nums[i], nums[i - 1]) can make elements from index 0 to i wiggle sorted. Hence, if [0 .. i-1] is already wiggle sorted, then we can maintain [0 .. i] wiggle sort through swapping i and i - 1.

T = O(N) and S = O(1).

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