280.Wiggle Sort

280. 摆动排序

题目大意:一串无规则数,要排成驼峰状,即a[1] , a[3], a[5] 比左右两侧的数都大(>=).

思路1:

先排序,然后插入新数组,时间复杂度:O(nlgn)+O(n)=O(nlgn),空间O(n).

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> res(n);  //辅助数组
        int i;
        for (i = 0; i < n/2; i++) {
            res[2*i] = nums[i];
            res[2*i+1] = nums[n-1-i];  //"驼峰"位置
        }
        if (n % 2 == 1) res[2*i] = nums[i];  //特殊处理
        nums = res;
    }
};

思路2：

一次遍历,a[i]与a[i-1]比较,当i时奇数时,a[i]应大于a[i-1],否则两元素交换.当i为偶数时,a[i]应小于a[i-1],否则交换.一遍下来就能保证奇数位置元素比两侧大.

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 1; i < n; i++) {
            if (i%2 && nums[i-1] > nums[i] || !(i%2) && nums[i-1] < nums[i]) {  //注意&&优先级大于||
                swap(nums[i-1], nums[i]);
            }
        }
    }
};