Leetcode.324.Wiggle Sort II

题目

给定一个数组，要求nums[0] < nums[1] > nums[2] < nums[3]....

Input: [1, 5, 1, 1, 6, 4]
Output: [1, 4, 1, 5, 1, 6]
Input: [4,5,5,6]
Output: [5,6,4,5]

思路

关键是倒序排列。

bool comp(int a,int b) {
    return a > b;
}

void wiggleSort(vector<int>& nums) {
    vector<int> temp = nums;
    sort(temp.begin(), temp.end(), comp);

    int k = 0;
    int j= ((int)nums.size())/2;

    for (int i = 0; i < nums.size(); i++) {
        if (i % 2 == 0) {
            nums[i] = temp[j++];
        } else {
            nums[i] = temp[k++];
        }
    }
}

总结

空间复杂度还有很大优化空间。