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.
参考了网上的写法。目前只想出nlogn的解法。
先对数组排序，然后将结果拷贝到另一个数组，因为数组已经排好序，所以一次从烤焙的数组的前一半，后一般取数据就好了。
举例：
假设已经排好序的数组：
[1,2,3,4,5]
那么首先设置两个指针：
i = (5+1) / 2 = 3
j = 5
（两个下标）
然后遍历原数组for int i = 0 ~ n
如果 i % 2 == 0 那么说明是奇数位，取copy[--i];
否则 取copy[--j];
这样就能够保证题目的要求。
代码：
public void wiggleSort(int[] nums) { Arrays.sort(nums); int[] copy = new int[nums.length]; for(int i=0;i<nums.length;i++){ copy[i] = nums[i]; } int i = (nums.length+1)/2; int j = nums.length; for(int k=0;k<nums.length;k++){ nums[k] = ((k & 1) == 0) ? copy[--i]: copy[--j]; } }
