给你一个整数数组 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] 同样是符合题目要求的结果,可以被判题程序接受。
示例 2:
输入:nums = [1,3,2,2,3,1]
输出:[2,3,1,3,1,2]
提示:
1 <= nums.length <= 5 * 104
0 <= nums[i] <= 5000
题目数据保证,对于给定的输入 nums ,总能产生满足题目要求的结果
进阶:你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/wiggle-sort-ii
普通思路 O(nlogn):由于要满足一大一小的关系,要想快速找到一大一小的数,我们可以先对他们进行排序,在排序之后,以中位数为准,显然右边的数都比左边的数大,所以我们可以把左右两边的数交替取值合并,就能得到“交替一大一小”的关系。
但是需要注意的是,如果与中位数值相等的数有多个,那么交替插入一大一小的数的时候就需要注意了,因为有可能出现相邻的两个数相同的情况。例如 [1,1,2,2,2,2,3,3],划分为[1,1,2,2]与[2,2,3,3],如果我们按顺序交替取值,合并的结果就是[1,2,1,2,2,3,2,3]。这是因为中间数2的数量太多,而且切分后,2还是相邻太近了。所以我们要让他们相互离得远一点,切分后,各自左右翻转180度。变成[2,2,1,1] [3,3,2,2],这样,两个数组的2就离得够远了。交替取值合并的结果就是[2,3,2,3,1,2,1,2]
所以整体思路就是:1.排序 2.划分 3.翻转 4.交替取值
在切分中,如果想把右边的数组交替插入到左边的数组,我们一般把元素较多的放在左边。我们知道:
1⃣️ n/2切分,左边的个数<=右边的个数;
2⃣️ (n+1)/2切分,左边的个数>=右边的个数;
例如,切分长度为5的数组,用 1⃣️ 切分,左边有2个,右边有3个;用 2⃣️ 切分,左边有3个,右边有2个。
所以我们会选择用 2⃣️ 切割。
当然,我们们也可以把切分点定为 n/2 + (n%2)
void wiggleSort(vector<int>& nums) {
//排序
sort(nums.begin(), nums.end());
int n = nums.size();
//切分
vector<int> A, B;
for (int i = 0; i < (n + 1) / 2; i++)A.push_back(nums[i]);
for (int i = (n + 1) / 2; i < n; i++)B.push_back(nums[i]);
//交替逆向取值
for (int i = 0; i < A.size(); i++)
nums[2 * i] = A[A.size() - 1 - i];
for (int i = 0; i < B.size(); i++)
nums[2 * i + 1] = B[B.size() - 1 - i];
}
进阶思路O(n):
我们只是想得到切分后的两个数组,且右边的所有数>=左边的所有数,这个时候,我们可以用“快速选择O(n)”,找出第n/2个数,找到后,左边的数都<=nums[n/2]小,右边都>=nums[n/2]。这个时候,我们那再用“三路划分O(n)”把中位数都集中放到中间,然后再“切分”、“翻转”、“交替取值”
void wiggleSort(vector<int>& nums) {
int n=nums.size();
auto mid_ptr = nums.begin()+n/2;
nth_element(nums.begin(),mid_ptr,nums.end());快速选择找到中位数
int mid = *mid_ptr;
//三路划分,让中位数集中到中间
int i=0,j=0,k=n-1;
for(int j=0;j<k;){
if(nums[j]<mid){
swap(nums[j++],nums[i++]);
}else if(nums[j]>mid){
swap(nums[j],nums[k--]);
}else{
j++;
}
}
if(n%2)mid_ptr++;
//切分左右数组
vector<int> A(nums.begin(),mid_ptr);
vector<int> B(mid_ptr,nums.end());
//逆向交替取值
for(int i=0;i<A.size();i++){
nums[2*i]=A[A.size()-1-i];
}
for(int i=0;i<B.size();i++){
nums[2*i+1]=B[B.size()-1-i];
}
}
终极思路:虚拟地址法,O(1)空间复杂度:
在上面的思路中,我们划分后,元素在数组中的位置还不是最终的位置。我们总是要把他们拿下来,然后交替放到最终位置。那我们能不能找到一种方法,在划分存放元素的时候,就自动存放到最终的位置呢?
我们可以建立一个“映射”,可以理解成是一个“通道”,如图,带箭头的线可以看作是通道,如果我们把数放在“虚地址”,它就会自动通过“通道”掉落到“实地址”即最终位置。
定义映射为:
#define A(i) nums[(1+2*(i)) % (n|1)]
按照这个道理,我们可以把“虚地址”看作是划分后元素临时存放的位置,“实地址”看作是元素最终存放的位置。我们在划分数组的时候,“较大的部分放在虚地址左边,较小的部分放在虚地址右边”
void wiggleSort(vector<int>& nums) {
int n=nums.size();
auto mid_ptr = nums.begin() + n/2;
nth_element(nums.begin(),mid_ptr,nums.end());//找中位数
int mid = *mid_ptr;
//映射
#define A(i) nums[(1+(i<<1)) % (n|1)]
//三路划分
int i=0,j=0,k=n-1;
while(j<=k){
if(A(j)>mid){
swap(A(i),A(j));
i++,j++;
}else if(A(j)<mid){
swap(A(k),A(j));
k--;
}else{
j++;
}
}
}
以上思路来自leetcode题解