LeetCode324. 摆动排序 II

题目描述

本题目来自LeetCode上的『324. 摆动排序 II』

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

示例1：

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

提示

1 <= nums.length <= 5 * 104
0 <= nums[i] <= 5000
题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

题解1 - 简单排序

考虑特殊情况：数组中不存在相同的元素，将数组排序后，从 中位数 处分成两个数组 $lnums$ 和 $rnums$，然后将两个数组交叉合并，即可得到一个摆动数组：
$$
lnums[0]<rnums[0]>lnums[1]<rnums[1]>…
$$

推广到一般情况：数组中存在相同的元素，那么可能有多个与中位数相同的数字，注意到中位数会出现在 $lnums$ 的尾部和 $rnums$ 首部，如果中位数的个数为 $(n+1)/2$，那么在合并后会出现中位数相邻的情况，如 $[1,2,2,2,3,4]$ 分成 $[1,2,2]$ 和 $[\dot{2},3,4]$ 交叉合并为 $[1,\dot{2},2,3,2,4]$，为了防止此情况发生，需要让中位数尽可能晚点相遇，可以将两个数组逆序为 $[2,2,1]$ 和 $[4,3,\dot{2}]$ 交叉合并为 $[2,4,2,3,1,\dot{2}]$。如果中位数的个数大于 $(n+1)/2$，那么不存在满足条件的摆动数组，因为无论怎样排序，都会有两个中位数相邻。

综上所述，将数组按升序排序，逆序遍历这个数组，先放入奇数位置，再放入偶数位置即可。这里选用了计数排序。

代码

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int backet[5010] = {0};
        int n = nums.size();
        for (const auto& num: nums) {
            ++backet[num];
        }
        int pos = 5000;
        for (int i = 1; i < n; i += 2) {
            while (backet[pos] == 0) {
                --pos;
            }
            nums[i] = pos;
            --backet[pos];
        }
        for (int i = 0; i < n; i += 2) {
            while (backet[pos] == 0) {
                --pos;
            }
            nums[i] = pos;
            --backet[pos];
        }
    }
};

复杂度分析

时间复杂度：$O(n+C)$，$C=5010$ 为值域大小。
空间复杂度：$O(C)$

题解2 - 快速选择 + 三路排序

根据题解1的分析，我们其实并不需要完全排序，只需要将数组根据中位数分成两个数组，因此直接找到中位数即可，此操作可通过 快速选择 实现。
C++ 提供了 std::nth_element 函数来进行快选，也可以自己构造，原理与快排类似。
找到中位数后，需要将小于中位数的放在数组的左边，大于中位数的放在数组的右边，此操作可通过三路排序实现。最后再交叉构造数组即可。

代码

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        nth_element(nums.begin(), nums.begin() + (n >> 1), nums.end());
        int mid = nums[n >> 1];

        int i = 0, j = 0, k = n;
        while (i < k) {
            if (nums[i] < mid) {
                swap(nums[i++], nums[j++]);
            } else if (nums[i] > mid) {
                swap(nums[i], nums[--k]);
            } else {
                ++i;
            }
        }
        
        vector<int> temp(nums);
        int pos = n - 1;
        for (i = 1; i < n; i += 2) {
            nums[i] = temp[pos--];
        }
        
        for (i = 0; i < n; i += 2) {
            nums[i] = temp[pos--];
        }
    }
};

复杂度分析

时间复杂度：快选和三路排序的复杂度均为 $O(n)$，整体为 $O(n)$
空间复杂度：快选的空间复杂度可优化为 $O(1)$，拷贝数组空间复杂度为 $O(n)$，总体为 $O(n)$。

题解3 - 优化空间

考虑不使用拷贝数组，直接在三路排序的过程中对原数组进行修改，可以建立一种映射，先遍历奇数下标，将大于中位数的元素都放在奇数下标中，小于中位数的元素都放在偶数下标中，等于中位数的元素会优先放入奇数下标。
定义映射 $f(idx)=(2 * idx + 1) % (n | 1)$。
可以在纸上模拟一遍。

代码

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        nth_element(nums.begin(), nums.begin() + (n >> 1), nums.end());
        int mid = nums[n >> 1];

        auto get = [&](int idx) -> int {
            return (2 * idx + 1) % (n | 1);
        };

        int i = 0, j = 0, k = n;
        while (i < k) {
            if (nums[get(i)] > mid) {
                swap(nums[get(i++)], nums[get(j++)]);
            } else if (nums[get(i)] < mid) {
                swap(nums[get(i)], nums[get(--k)]);
            } else {
                ++i;
            }
        }
    }
};