【leetcode】324. 摆动排序 II

题目内容

324. 摆动排序 II

思路分析

参考资料1---题解1---方法一、方法二、方法三

参考资料2---题解2--方法一

参考资料3---荷兰国旗问题wiki---方法二

参考资料4---【leetcode】75. 颜色分类 ---方法二

参考资料5---快速选择算法---方法二

参考资料6---时间复杂度近似O(N),空间复杂度O(1)的方法---方法二、方法三

方法一：先排序再倒序穿插

解决本题可以采用以下方法：

先将数组排序，如排序后变为[1,2,3,4,5,6]
然后将数组分为两部分，如第一部分为[1,2,3]，第二部分为[4,5,6]
再将两部分穿插，得到[1,4,2,5,3,6]

然而本题的难点在于[1,2,2,3]这种情况，这时再按上面的做法，将会得出[1,2,2,3]的答案，是不符合要求的。这种现象出现的原因在于第一部分的尾和第二部分的头在穿插后离得太近。解决此问题的办法为倒序穿插。即

[2,x,1,x]
    ↓
[2,3,1,2]

方法二：快速选择+三分法（3-way-partition）

如参考资料一所述，本题只关心中位数所在的位置，以及中位数的左边都小于中位数，中位数的右边都大于中位数，不需要对数组进行排序，因此可以将时间复杂度从O(nlogn)降为O(n)。

从无序数组中找出中位数，应该想到快速选择算法，该算法可以从数组中选出第K个位置的数。这里使用C++的nth_element来实现。关于快速选择，详见资料5。

当找出中位数后，有可能遇到以下情况：2，4，3，6，7，9，7，7，7。即中位数被选出来了，但仍然有中位数散落在某一边。这个问题和荷兰国旗问题（即资料4的题目）的0，1，2排序异曲同工，可以使用三分法进行排序，最终期望的目的是中位数都集中在中间部分，小于中位数的在左边，大于中位数的在右边。

这里使用的是资料3wiki中的算法，和之前做资料4题目时的算法实现上略有不同，代码中对算法进行了解读。

方法三：快速选择 + 三分法（3-way-partition）+ 虚拟地址

虚拟地址有点绕，为便于理解，照着资料1手动举例还原一遍算法过程

数组nums：

nums[i]	3	5	1	1	1	6	5
i	0	1	2	3	4	5	6

nums找中位数后：

nums[i]	1	1	1	4	6	5	4
i	0	1	2	3	4	5	6

映射规则：设数组大小为n，则

i=1,3,5,...  -> j=0,1,2,...n/2-1
i=0,2,4,... -> j=n/2, n/2+1, ... n-1

虚拟映射后的数组A[j]：

A[j]	1	4	5	1	1	6	4
j	0	1	2	3	4	5	6
对应的i	1	3	5	0	2	4	6

对A[j]使用三分法后（将大的部分放在左边）：

A[j]	6	5	4	4	1	1	1
j	0	1	2	3	4	5	6
对应的i	1	3	5	0	2	4	6

此时的nums数组：

nums[i]	4	6	1	5	1	4	1
i	0	1	2	3	4	5	6

确实完成了摆动排序。

该算法的映射十分巧妙，解决了前两个办法空间复杂度为O(n)的问题，没有占用额外的空间。它在三分法时通过映射也完成了倒序插入的工作。感觉理解该算法的核心在于倒数第二个表格。排序后的A数组的前半部分（大数及中间数）其实对应nums数组的1,3,5，而后半部分（中间数及小数）其实对应nums数组的0,2,4,6。

另外，映射宏为\#define A(i) nums[(1+2*(i)) % (n|1)]，n|1是按位或，利用了奇数的二进制表示最后有1，而偶数的二进制表示最后没1的特点，若n为奇数，则n|1为n，若n为偶数，则n|1为n+1。使用该式可完成想要的映射。（原理不清楚😵 实际验证确实可以，只能说数学好神奇吧。。。）要是会自己写映射的话我会让三分法时能正常分，不要大的在左小的在右，怪怪的。

代码

#include <vector>
#include <math.h>
#include <limits.h>
#include <algorithm>

using namespace std;

// 先排序再倒序穿插
// 时间复杂度O(nlogn)
// 空间复杂度O(n)
class Solution1 {
public:
    void quickSort(vector<int>& nums, int left, int right) {
       // 注意点1，left>=right时就可以返回了，是可以取到等号的
       if (left >= right) return;
       
       int pivot = nums[left];

       int i = left, j = right;

       while (i != j) {
          // 找到第一个小于等于pivot的数停下
          // 注意点2：需要先从右往左找，保证再在小于等于区相遇
          while (nums[j] > pivot && i < j) {
             --j;
          }
          
          // 找到第一个大于pivot的数停下
          while (nums[i] <= pivot && i < j) {
             ++i;
          }

          swap(nums[i], nums[j]);
       }

       // 此时两指针相遇于小于等于区，即left==right
       // 交换nums[left]与pivot
       // 注意点3：并不是nums[i]与nums[0]交换，而是与nums[left]交换，而且可以用赋值
       //         优于交换。
       //swap(nums[i], nums[0]);
       nums[left] = nums[i];
       nums[i] = pivot;

       // 对左右两边进行快排
       quickSort(nums, left, i - 1);
       quickSort(nums, i + 1, right);
    }

    void quickSort(vector<int>& nums) {
       quickSort(nums, 0, nums.size() - 1);
    }

    void wiggleSort(vector<int>& nums) {
       int n = nums.size();
       quickSort(nums);
       vector<int> temp(nums);
       int j = n;
       // 两个for循环有先后顺序
       // 注意题目中要求nums[0] < nums[1]
       for (int i = 1; i < n; i += 2) {
          nums[i] = temp[--j];
       }
       for (int i = 0; i < n; i += 2) {
          nums[i] = temp[--j];
       }
    }
};

// 快速选择 + 3分法
// 时间复杂度O(n)
// 空间复杂度O(n)
class Solution2 {
public:
    // from https://en.wikipedia.org/wiki/Dutch_national_flag_problem
    void threeWayPartition(vector<int>& nums, int target) {
       // 使用三指针，i,j,k。j负责向前扫描
       // i负责指示小数的范围，k负责指示大数的范围
       int i = 0, j = 0;
       int k = nums.size() - 1;
       while (j <= k) {
          if (nums[j] < target) {
             // j扫描到小数
             // 当i=j时，相当于两个指针都往前一位
             // 当i<j时，相当于将j路上遇到的小数都往前换，i+1代表小数的范围+1
             swap(nums[i], nums[j]);
             ++i;
             ++j;
          } else if (nums[j] > target) {
             // j扫描到大数
             // 将j遇到的大数往后换，缩小大数范围
             // 同时不知道换过来的数的情况，因此j不动，下次扫描换过来的数
             swap(nums[j], nums[k]);
             --k;
          } else {
             // j扫描到中间数，则继续向前
             // 因此i所指向的不是原本的中间数就是换过来的中间数，因此i和j位置上的数互
             // 相换位后j不需要再判断从i缓过来的数的情况
             ++j;
          }
          // 直到j与k相遇，排序完毕
       }
    }
    void wiggleSort(vector<int>& nums) {
       int n = nums.size();
       
       // 快速选择
       nth_element(nums.begin(), nums.begin() + n/2, nums.end());
       int median = nums[n/2];

       // 3分法
       threeWayPartition(nums, median);

       // 反序穿插
       vector<int> temp(nums);
       int j = n;
       for (int i = 1; i < n; i+=2) {
          nums[i] = temp[--j];
       }
       for (int i = 0; i < n; i+=2) {
          nums[i] = temp[--j];
       }
    }
};

// 快速选择 + 3分法 + 虚拟地址
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
       int n = nums.size();

       // 快速选择
       nth_element(nums.begin(), nums.begin() + n/2, nums.end());
       int median = nums[n/2];

       // 地址映射
       // 将nums[0],nums[1],nums[2]...映射为A[0],A[1],A[2]
       #define A(x) nums[(1+2*(x)) % (n|1)]

       // 三分法 但要将大的放在左边
       int i = 0, j = 0, k = n - 1;
       while (j <= k) {
          if (A(j) > median) {
             swap(A(i), A(j));
             ++i;
             ++j;
          } else if (A(j) < median) {
             swap(A(j), A(k));
             --k;
          } else {
             ++j;
          }
       }
    }
};

int main() {
   Solution s;
   vector<int> input{ 1,3,2,2,3,1 };
   s.wiggleSort(input);
   int a = 0;
}

收获

一道题目做了好几天，虽然难，但还是硬着头皮做下来了，还是有一定的收获。对于做过的荷兰国旗问题有了更深的理解，掌握了快速选择算法，最后的虚拟地址虽然没完全掌握，但也有了一定的了解，希望以后能想起来类似的思路。