题目描述
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….
Example1:
Input: nums = [1, 5, 1, 1, 6, 4] Output: One possible answer is [1, 4, 1, 5, 1, 6].
Example2:
Input: nums = [1, 3, 2, 2, 3, 1] Output: One possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
解题思路
- 我们通过使用辅助数组，将数组排序后分成两半
- 来实现 上升 下降 上升 下降的序列
- 很明显需要从 前半段 抽一个 从后半段抽一个 这样就能符合题意
class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> tmp(nums);
sort(tmp.begin(), tmp.end());
int i = (nums.size() - 1) / 2;
int j = nums.size() - 1;
int k = 0;
while(k < nums.size()){
if((k & 1) == 0){
nums[k++] = tmp[i--];
}else{
nums[k++] = tmp[j--];
}
}
}
};
