Given an unsorted array nums
, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]...
.
Example:
Input: nums = [3,5,2,1,6,4]
Output: One possible answer is [3,5,1,6,2,4]
A:
-------先来个 构造法 -------- 排序,然后每2个位置,互换
class Solution { public: void wiggleSort(vector<int>& nums) { sort(nums.begin(), nums.end()); int n = nums.size(); for(int i = 1;i+1<n;i+=2){ //swich i, and i+1 position int tmp = nums[i]; nums[i] = nums[i+1]; nums[i+1] = tmp; } } };
然而上面的代码明显不是最优的。
考虑到我们允许 == 因此可以直接反复交换
class Solution { public: void wiggleSort(vector<int>& nums) { int tmp=0; for(int i = 0; i+1 < nums.size(); i++){ if(i&1){// position 1,3,5... if(nums[i] < nums[i+1]){ //swich i, and i+1 position tmp = nums[i]; nums[i] = nums[i+1]; nums[i+1] = tmp; } }else{ // position 0 2,4,6,8 if(nums[i] > nums[i+1]){ //swich i, and i+1 position tmp = nums[i]; nums[i] = nums[i+1]; nums[i+1] = tmp; } } } } };
No comments:
Post a Comment