题目描述
Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
You may assume the input array always has a valid answer.
Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?
Example 1:
Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.Example 2:
Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]方法一：排序+双指针
先把数组进行排序，然后再通过双指针进行逐个插入。
这里需要思考的是怎么插入。我们可以将排序好的数组分成两份：前面一半较小的以及后面一半较大的。然后将较大的一半插入到奇数下标中，较小的一半插入偶数下标中，这样一定能保证Wiggle Sort。也就是说奇数下标的数据一定小于等于中位数，偶数下标的数据一定大于中位数！！！
需要注意的是，如果总共有奇数个，中位数的下标在(nums.length - 1) / 2，如果有偶数个，中位数较小的那个数也在(nums.length - 1) / 2。所以左指针取left= (nums.length - 1) / 2开始递减，右指针就取最后一个开始递减。
代码
class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> tmp = nums;
sort(tmp.begin(),tmp.end());
int n = nums.size();
int l = (n - 1)/2, r = n -1;
for(int i = 0;i<n;++i){
if(i%2==0){
nums[i] = tmp[l--];
}else{
nums[i] = tmp[r--];
}
}
}
};复杂度分析
- 时间复杂度：\(O(nlogn)\)，排序所需的时间复杂度是\(O(nlogn)\)，插入\(O(n)\)，整体\(O(nlogn)\)
- 空间复杂度：\(O(n)\)，需要额外的空间存放排序的元素。
方法二：桶排序
我们可以把所有的元素分桶然后逐个取出。由于数据大小最大是5000，我们可以开5001个桶来存放元素。然后从大到小依次放回原数组。
同样的思路，我们需要在奇数下标插入比中位数小的数，偶数下标插入比中位数大的数。但是这一次我们不知道中位数在桶中的下标。没关系，我们可以从大到小先每隔一位插一个偶数下标的桶，插完后自然剩下的就是小于等于中位数的值，再从大到小插到奇数下标处。
代码
public void wiggleSort(int[] nums) {
//5001个桶
int[] bucket = new int[5001];
for (int num : nums) {
bucket[num]++;
}
int j = 5000;
//插空放 较大元素
for (int i = 1; i < nums.length; i += 2) {
while (bucket[j] == 0) {//不是每一个桶都有数，用while过滤
j--;
}
nums[i] = j;
bucket[j]--;
}
//插空放 较小元素
for (int i = 0; i < nums.length; i += 2) {
while (bucket[j] == 0) {
j--;
}
nums[i] = j;
bucket[j]--;
}
}复杂度分析
- 时间复杂度：\(O(n)\)，装桶\(O(n)\)，插入\(O(n)\)，整体\(O(n)\)
- 空间复杂度：\(O(c)\)，需要额外的桶空间，这里c = 5001
方法三：快选 + 三数排序
本质上，题目要我们实现一种构造方法，能够将 nums 调整为满足「摆动」要求。
具体的构造方法：
- 找到 nums 的中位数，这一步可以通过「快速选择」算法来做，时间复杂度为 \(O(n)\)，空间复杂度为 \(O(\log{n})\)，假设找到的中位数为 x；
- 根据 \(nums[i]\)与 x 的大小关系，将 \(nums[i]\)分为三类（小于/等于/大于），划分三类的操作可以采用「三数排序」的做法，复杂度为 \(O(n)\)。
这一步做完之后，我们的数组调整为：\([a_1, a_2, a_3, ... , b_1, b_2, b_3, ... , c_1, c_2, c_3]\)，即分成「小于 x / 等于 x / 大于 x」三段。
- 构造：先放「奇数」下标，再放「偶数」下标，放置方向都是「从左到右」（即可下标从小到大进行放置），放置的值是则是「从大到小」。
到这一步之前，我们使用到的空间上界是 \(O(\log{n})\)，如果对空间上界没有要求的话，我们可以简单对 nums 进行拷贝，然后按照对应逻辑进行放置即可，但这样最终的空间复杂度为 \(O(n)\)（代码见 P2）；如果不希望影响到原有的空间上界，我们需要额外通过「找规律/数学」的方式，找到原下标和目标下标的映射关系（函数 getIdx 中）。
容易证明该构造过程的正确性（即该构造过程必然能顺利进行）：由于我们是按照值「从大到小」进行放置，如果构造出来的方案不合法，必然是相邻的两个值为相等（“应当递增实际递减”或者“应当递减实际递增”的情况已被「从大到小」进行放置所否决），而当相邻位置放置了相同的值，即存在某个奇数下标，以及其相邻的偶数下标都放置了相同的值，这等价于该值出现次数超过总个数的一半，这与「题目本身保证数据能够构造出摆动数组」所冲突。
代码
快速选择算法可以用递归表达找第k大的数：
int[] nums;
int qselect(int l, int r, int k) {
if (l == r) return nums[l];
int x = nums[l + r >> 1], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) swap(i, j);
}
int cnt = j - l + 1;
if (k <= cnt) return qselect(l, j, k);
else return qselect(j + 1, r, k - cnt);
}
void swap(int a, int b) {
int c = nums[a];
nums[a] = nums[b];
nums[b] = c;
}或者非递归方式找第k大的数：
int findKthLargest(int[] nums, int k) {
int lo = 0, hi = nums.length - 1;
// 索引转化，第k大的数就是第 n - k小的数
k = nums.length - k;
while (lo <= hi) {
// 在 nums[lo..hi] 中选一个分界点
int p = partition(nums, lo, hi);
if (p < k) {
// 第 k 大的元素在 nums[p+1..hi] 中
lo = p + 1;
} else if (p > k) {
// 第 k 大的元素在 nums[lo..p-1] 中
hi = p - 1;
} else {
// 找到第 k 大元素
return nums[p];
}
}
return -1;
}
//每一次都保证pivot位置的数值是最终正确的位置的数值
int partition(int[] nums, int lo, int hi) {
if (lo == hi) return lo;
// 将 nums[lo] 作为默认分界点 pivot
int pivot = nums[lo];
// j = hi + 1 因为 while 中会先执行 --
int i = lo, j = hi + 1;
while (true) {
// 保证 nums[lo..i] 都小于 pivot
while (nums[++i] < pivot) {
if (i == hi) break;
}
// 保证 nums[j..hi] 都大于 pivot
while (nums[--j] > pivot) {
if (j == lo) break;
}
//退出while循环条件
if (i >= j) break;
// 如果走到这里，一定有：
// nums[i] > pivot && nums[j] < pivot
// 所以需要交换 nums[i] 和 nums[j]，
// 保证 nums[lo..i] < pivot < nums[j..hi]
swap(nums, i, j);
}
// 将 pivot 值交换到正确的位置
swap(nums, j, lo);
// 现在 nums[lo..j-1] < nums[j] < nums[j+1..hi]
return j;
}
// 交换数组中的两个元素
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}class Solution {
int[] nums;
int n;
int qselect(int l, int r, int k) {
if (l == r) return nums[l];
int x = nums[l + r >> 1], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) swap(i, j);
}
int cnt = j - l + 1;
if (k <= cnt) return qselect(l, j, k);
else return qselect(j + 1, r, k - cnt);
}
void swap(int a, int b) {
int c = nums[a];
nums[a] = nums[b];
nums[b] = c;
}
public void wiggleSort(int[] _nums) {
nums = _nums;
n = nums.length;
int x = qselect(0, n - 1, n + 1 >> 1);
int l = 0, r = n - 1, loc = 0;
//三数排序
while (loc <= r) {
if (nums[loc] < x) swap(loc++, l++);
else if (nums[loc] > x) swap(loc, r--);//注意这里没有++！！！保证小与x的数有序！
else loc++;
}
int[] clone = nums.clone();
int idx = 1; loc = n - 1;
while (idx < n) {
nums[idx] = clone[loc--];
idx += 2;
}
idx = 0;
while (idx < n) {
nums[idx] = clone[loc--];
idx += 2;
}
}
}带上getId，代码变为
int getIdx(int x) {
return (2 * x + 1) % (n | 1);
}
public void wiggleSort(int[] _nums) {
nums = _nums;
n = nums.length;
int x = qselect(0, n - 1, n + 1 >> 1);
int l = 0, r = n - 1, loc = 0;
while (loc <= r) {
if (nums[getIdx(loc)] > x) swap(getIdx(loc++), getIdx(l++));
else if (nums[getIdx(loc)] < x) swap(getIdx(loc), getIdx(r--));
else loc++;
}
}复杂度分析
- 时间复杂度：快选的时间复杂度为 \(O(n)\)；三数排序复杂度为 \(O(n)\)。整体复杂度为 \(O(n)\)
- 空间复杂度：我的习惯是不算递归带来的额外空间消耗的，但如果是题目指定 \(O(1)\)空间的话，显然是不能按照习惯来，快选的空间复杂度为 \(O(\log{n})\)。整体复杂度为 \(O(\log{n})\)