Wiggle Sort(Medium)

题目描述

Given an unsorted array nums, reorder it in-place such that

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

!Notice
Please complete the problem in-place.

解题思路

• 思路一：

  • 利用quick sort
  • 时间复杂度：$$O(n \times \log^n)$$

• 思路二：

  • 贪心
  • 时间复杂度：$$O(n)$$

参考代码

思路一：（快排）

class Solution {
public:
    /**
     * @param nums a list of integer
     * @return void
     */  
    void wiggleSort(vector<int>& nums) {
        // Write your code here
        int n = nums.size();
        quick_sort(0, n - 1, nums);
        for (int i = 1; i < n; i += 2) {
            if (i + 1 < n) swap(nums[i], nums[i + 1]);
        }
    }

    void quick_sort(int l, int r, vector<int> &nums) {
        if (l < r) {
            int pivot = nums[l];
            int p = l, q = r + 1;
            while ( p < q ) {
                while (nums[++ p] < pivot);
                while (nums[-- q] > pivot);
                if (p < q) {
                    swap(nums[p], nums[q]);
                }
            }
            swap(nums[l], nums[q]);
            quick_sort(l, q - 1, nums);
            quick_sort(q + 1, r, nums);
        }
    }
};

思路二：（贪心）

class Solution {
public:
    /**
     * @param nums a list of integer
     * @return void
     */  
    void wiggleSort(vector<int>& nums) {
        // Write your code here
        int n = nums.size();
        for (int i = 1; i < n; ++ i) {
            if (i % 2 == 1 && nums[i] < nums[i - 1]
                || i % 2 == 0 && nums[i] > nums[i - 1]) {
                    swap(nums[i], nums[i - 1]);
                }
        }
    } 
};