LeetCode 324 Wiggle Sort II

Posted on | In | 阅读 
摇摆排序，要求nums[0] < nums[1] > nums[2] < nums[3]... 且时间复杂度为O(n)，额外空间为O(1)

  1. 如果没有时间复杂度要求，做法应该为先排序，然后将后半个数组穿插到前半个数组中。但如果不能够排序，我们就只能通过求中位数的方法来完成。再加上空间显示，则使用交换的方法来完成排序。

  2. 求中位数

    算法为O(n)，使用一趟快速排序，将数组分为两份，然后在多的那部分中继续一趟快速排序，直到正好以中位数为sentinel，最多计算次数不超过2n。使用nth_element函数找到数组中第n大的数能够直接完成这个过程，完成后，中位数左边的数都比它小，右边的都比它大；

  3. 两个指针low，high，分别从奇数位正向遍历1、3、5……以及偶数位反向遍历……4、2、0。用(i*2 + 1) / (size - 1)来按照1、3、5……0、2、4……的顺序重排数组；然后按这个顺序开始，如果小于中位数，就放到low左边，如果大于中位数就放到high右边。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int sz = nums.size();
        nth_element(nums.begin(), nums.begin() + sz / 2, nums.end());
        auto index = [=](int pos) {return (pos * 2 + 1) % (sz | 1);};
        int mid = nums[sz/2];
        int low = 0, high = sz-1;
        int i = 0;
        while(i <= high) {
            if(nums[index(i)] < mid) {
                swap(nums[index(i)], nums[index(high--)]);
            }else if(nums[index(i)] > mid) {
                swap(nums[index(i++)], nums[index(low++)]);
            }else {
                ++i;
            }
        }
    }
};