508-摆动排序

给你一个没有排序的数组，请将原数组就地重新排列满足如下性质

nums[0] <= nums[1] >= nums[2] <= nums[3]....

注意事项

请就地排序数组，也就是不需要额外数组

样例

给出数组为 nums = [3, 5, 2, 1, 6, 4] 一种输出方案为 [1, 6, 2, 5, 3, 4]

标签

排序 快速排序 数组 谷歌

方法一（快排 + 交换，时间复杂度O(nlgn)）

先将数组排序，然后交换第2位和第3位，第3位和第4位...

code

class Solution {

public:

    /**

     * @param nums a list of integer

     * @return void

     */

    void wiggleSort(vector<int>& nums) {

        // Write your code here

        int size = nums.size();

        if (size <= 0) {

            return;

        }

        sort(nums.begin(), nums.end());

        for (int i = 1; i < size - 1; i += 2) {

            swap(nums[i], nums[i + 1]);

        }

    }

};

方法二（找规律 + 交换，时间复杂度O(n)）

• 当i为奇数时，nums[i] >= nums[i - 1]
• 当i为偶数时，nums[i] <= nums[i - 1]
• 那么只要对每个数字，根据其奇偶性，选择是否与上一个数交换即可

code

class Solution {

public:

    /**

     * @param nums a list of integer

     * @return void

     */

    void wiggleSort(vector<int>& nums) {

        // Write your code here

        int size = nums.size();

        if (size <= 0) {

            return;

        }

        for (int i = 1; i < size; i += 2) {

            if ((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) {

                swap(nums[i], nums[i - 1]);

            }

        }

    }

};