leetcode-324-摆动排序 II-java

题目及测试

package pid324;
/*  摆动排序 II
给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
示例 1:
输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:
输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
说明:
你可以假设所有输入都会得到有效的结果。
进阶:
你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
*/
 
 
public class main {
	
	public static void main(String[] args) {
		int[][] testTable = {
  {1, 5, 1, 1, 6, 4},{1, 3, 2, 2, 3, 1},{1,0,1,3,0,4,0,2,0,2},{0,6,2,7,0}};
		for (int[] ito : testTable) {
			test(ito);
		}
	}
		 
	private static void test(int[] ito) {
		Solution solution = new Solution();
		long begin = System.currentTimeMillis();
		for (int i = 0; i < ito.length; i++) {
		    System.out.print(ito[i]+" ");		    
		}
		System.out.println();
		//开始时打印数组
		
		 solution.wiggleSort(ito);//执行程序
		long end = System.currentTimeMillis();	
		
		//System.out.println(ito + ": rtn=" + rtn);
		System.out.println("rtn=" );
		for (int i = 0; i < ito.length; i++) {
		    System.out.print(ito[i]+" ");
		}//打印结果几数组
		
		System.out.println();
		System.out.println("耗时：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}
 
}

没想出来

解法1（别人的）

有一个数组[a1,a2,...,an]，我们怎么把它排成摇摆序列呢？

由摇摆序列的定义:nums[0] < nums[1] > nums[2] < nums[3]...，我们知道了可以分成较大一部分的数和较小一部分数，然后互相穿插即可。比如一个数组排序后为：A=[a1,a2,...,an] (a1<=a2<=....<=an)，然后分成较小和较大的两部分[a1,a2,...,a(n/2)]，[a(n/2+1),...,an]（数组长度为奇数时不影响），再进行穿插操作。
那是不是穿插成[a1,a(n/2+1),a2,a(n/2+2),...,an]就行了呢？

其实不对，可以验证特殊情况：n比较小时且为偶数时，穿插后的序列需要满足a(n/2+1)>a2，如果a1<a2<=a(n/2+1)<an，a(n/2+1)正好是a2的后一项且与a2相等呢？即如果是[4,5,5,6]的情况呢？
那就分成了[4,5]，[5,6]两部分，之后穿插成的是[4,5,5,6]并不是摇摆序列。
应该怎样排列呢？

为了方便阅读，我们在下文中定义较小的子数组为数组A，较大的子数组为数组B。显然，出现上述现象是因为nums中存在重