324. 摆动排序 II

324. 摆动排序 II

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> A(nums.begin(), nums.begin() + (n + 1) / 2);
        vector<int> B(nums.begin() + (n + 1) / 2, nums.end());
        // 如果A,B中有重复数字的话，肯定是分别出现在A的结尾和B的开头，为了防止他们会合，必须让他们隔开来，所以2个都进行倒序遍历就可以隔开来了
        int pa = A.size() - 1, pb = B.size() - 1;
        for(int i = 0; i < n; i += 2)
        {
            nums[i] = A[pa--];
            if(pb >= 0)
                nums[i + 1] = B[pb--];
        }
    }
};

T(n): O(nlogn)

S(n): O(n)

快速选择+三分+穿插

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return;
        auto midPtr = nums.begin() + (n + 1) / 2;
        nth_element(nums.begin(), midPtr, nums.end());
        int midNum = *midPtr;
        int i = 0, j = 0, k = n - 1;
        // 因为nth_element只能使第n小的数字在n处，如果有重复数字的情况下，其他和中位数相等的数字是无法确定他们和中位数相邻的，所以需要进行三分，把原数组划为小于中位数，等于中位数，大于中位数三个部分。
        // i表示小于中位数的指针，j表示遍历用的指针，也指向中位数，k表示大于中位数部分的指针
        // 以下while表示三分算法，T(n)为O(n)
        // 所以当nums[j] > midNum时，说明j走到了大于中位数的区块，这时缓过来的nums[k]有可能还大于中位数，所以j不能++，要留给下一步再判断
        // 当nums[j] < midNum，说明j在小于中位数的区块行走，此时，当nums[j]等于中位数时，j会加一，而i停留，由此，所有小于中位数的数都会交换到前面，而等于中位数的数会逐渐被挤到中间。
        while(j < k)
        {
            if(nums[j] > midNum)
                swap(nums[j], nums[k--]);
            else if(nums[j] < midNum)
                // 这里j可以++是因为换过来的nums[i]必然是等于中位数的数，否则j和i就是同步走的了
                swap(nums[j++], nums[i++]);
            else
                ++j;
        }
        vector<int> A(nums.begin(), midPtr);
        vector<int> B(midPtr, nums.end());
        for(int i = A.size() - 1, j = 0; i >= 0; j += 2, --i)
            nums[j] = A[i];
        for(int i = B.size() - 1, j = 1; i >= 0; j += 2, --i)
            nums[j] = B[i];
    }
};

T(n) : O(n)

S(n): O(n)

nth_element进行自己的实现

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return;
        quickSort(nums, 0, n - 1, (n + 1) / 2);
        auto midPtr = nums.begin() + (n + 1) / 2;
        int midNum = *midPtr;
        int i = 0, j = 0, k = n - 1;
        while(j < k)
        {
            if(nums[j] > midNum)
                swap(nums[j], nums[k--]);
            else if(nums[j] < midNum)
                swap(nums[j++], nums[i++]);
            else
                ++j;
        }
        vector<int> A(nums.begin(), midPtr);
        vector<int> B(midPtr, nums.end());
        for(int i = A.size() - 1, j = 0; i >= 0; j += 2, --i)
            nums[j] = A[i];
        for(int i = B.size() - 1, j = 1; i >= 0; j += 2, --i)
            nums[j] = B[i];
    }
private:
    // 本质就是快速排列，然后只取一部分，所以舍去了
    void quickSort(vector<int>& nums, int lo, int hi, int n)
    {
        if(lo > hi)
            return;
        auto pivot = rand() % (hi - lo + 1) + lo;
        swap(nums[pivot], nums[lo]);
        int c = nums[lo];
        int i = lo, j = hi + 1;
        while(i < j)
        {
            while(i < hi && nums[++i] <= c) {}
            while(j > lo && nums[--j] >= c) {}
            if(i >= j)
                break;
            swap(nums[i], nums[j]);
        }
        swap(nums[lo], nums[j]);
        if(j < n)
            quickSort(nums, j + 1, hi, n);
        else if(j > n)
            quickSort(nums, lo, j - 1, n);
        else
            return;
    }
};

关于nth_element的时间复杂度分析

假设k次迭代终止，假设迭代平衡

T(n) = T(n / 2) + n = T(n / 4) + n / 2 + n...

当迭代次数趋于无穷的时候

T(n) = n