Wiggle Sort II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example: (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note: You may assume all input has valid answer.
Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?
- 三路合并
- quick select
- 索引的改变
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n=nums.size();
auto mid=nums.begin()+n/2;
nth_element(nums.begin(),mid,nums.end());
#define A(i) nums[(2*(i)+1)%(n|1)]
int midVal=*mid;
int i=0,j=0,k=nums.size()-1;
while(j<=k)
{
if(A(j)>midVal)
swap(A(i++),A(j++));
else if(A(j)<midVal)
swap(A(j),A(k--));
else j++;
}
}
};
三路合并代码：
procedure three-way-partition(A : array of value, mid : value):
i ← 0
j ← 0
n ← size of A - 1
while j ≤ n:
if A[j] < mid:
swap A[i] and A[j]
i ← i + 1
j ← j + 1
else if A[j] > mid:
swap A[j] and A[n]
n ← n - 1
else:
j ← j + 1
参考：