正文
leetcode 280.Wiggle Sort 、324. Wiggle Sort II
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
这两个题可以理解为奇数位大于相邻两个偶数位，这两个题的输入数组是相同的，即数组中数值无序，且可能有相等的数值。但Wiggle Sort II要求是奇偶位的只能大于，不能等于。
无论是280.Wiggle Sort还是324. Wiggle Sort II，都可以通过排序，然后以中间值为分界分成a、b两部分，每次先从a中选择一个数，然后再从b中选择一个数组成新的数组就是锯齿状的数组了，如下图。
但是这种方式，时间复杂度是O(NlogN),空间是O(N)，因为你需要重新申请一个数组。
Wiggle Sort:
注意：解法一是每次i增加2，题目不是保证3个3个的情况，而是整个数组都要满足要求。
解法一错误版本：
如果nums的长度是4，这种情况下nums[i+1]会越界。但是如果你用的是i和i-1的组合，一定可以不会越界，因为i不越界i-1就一定不会越界，for循环控制i，i越界了整个循环就结束了。
class Solution {
public:
void wiggleSort(vector<int>& nums) {
sort(nums.begin(),nums.end());
for(int i = ;i < nums.size();i += ){
swap(nums[i],nums[i+]);
}
return;
}
};
解法一正确版本：
如果没有if这个语句，当nums.size() <= 2时，for循环里的nums[i]会出现数组越界
class Solution {
public:
void wiggleSort(vector<int>& nums) {
sort(nums.begin(),nums.end());
if(nums.size() <= )
return;
for(int i = ;i < nums.size();i += )
swap(nums[i],nums[i-]);
return;
}
};
解法二
时间复杂度为O(n)，空间复杂度为O(1)。
这个代码无法跑Wiggle Sort II，还是在有相同数字的时候出错，比如输入是[4,5,5,6]，输出变成[4,5,5,6]
https://www.cnblogs.com/grandyang/p/5177285.html
class Solution {
public:
/*
* @param nums: A list of integers
* @return: nothing
*/
void wiggleSort(vector<int> &nums) {
// write your code here
for(int i = ;i < nums.size();i++){
if((i% == && nums[i] < nums[i-]) || (i% == && nums[i] > nums[i-]))
swap(nums[i],nums[i-]);
}
}
};
324. Wiggle Sort II
解法一
这个解法和Wiggle Sort的解法一类似，先排序，然后再让奇偶位保持锯齿状。但Wiggle Sort解法一的代码不适合Wiggle Sort II，因为Wiggle Sort II要求不能相等，所以针对输入数组中有相同数字的情况就不能正确解决。
比如：
[1,5,1,1,6,4]就会错误生成
[1,1,5,6,1,4]，不过针对没有相同数字的数组解法一也是可以的。
与1不同，这个不能为等号。排序后，两个指针，一个从中间往前，一个从末尾往前。j、k的初始化这注意，必须保证0～j比j+1～k大于等于1个，这样才能填满。这个的空间复杂度就为O(n)了。
class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> tmp = nums;
sort(tmp.begin(),tmp.end());
int j = (nums.size() - )/,k = nums.size() - ;
for(int i = ;i < nums.size();i++){
nums[i] = i % ? tmp[k--] : tmp[j--];
}
return;
}
};
http://www.cnblogs.com/grandyang/p/5139057.html
