leetcode 280. Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
原题地址

原理很简单，如果发现有违反规则的就跟前一个交换。一开始理解这道题认为就是一大一小交替排列，跑了一遍发现第一个必须是小。代码如下：

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

看了网上的答案，发现我的脑回路果然跟主流的不一样XD。正常的思路应该是，奇数位的要比前面大，偶数位的要比前面小。代码如下：

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