[Algorithm]Reorder Array

Given an array with distinct elements a1, a2, a3...., reorder it as a1 < a2 > a3 < a4 >.......

对于这一题我们可以先分析array是sorted的话，我们的解法应该是什么样

• 如果array是偶数长度的话，我们只要从(a2，an-1）这一对开始每隔一对交换一对直到我们到达中间一对即可，这样可以的原因是比如我们交换a2这一对的时候换回来的值可以保证a1 < a2 > a3，对于a4那一对是一样的，注意只有长度为偶数的时候这个方法才work，是奇数的话中间总会三个是递增或者递减的，这是因为交换后中间元素的两边同时被交换的元素影响了。
• 如果array是奇数的话，我们把它转化成偶数即可，我们除掉第一个元素，剩下的元素是长度为偶数的数组，同时a1满足a1< a2（交换后的a2）的条件

所以，如果数组是sorted的话，我们用n / 2次交换就可以完成，如果数组不是sorted的话，我们进行n次交换也可以完成，具体的思想是如果A[k]和A[k+ 1]如果不满足他们应该有的关系，就交换，下面我们证明这样是可行的：

• 如果实际上A[k] < A[k + 1]，但他们的关系应该是A[k] > A[k + 1]。因为A[k]之前的部分是reordered的，我们可以得知A[k - 1] < A[k]，那么实际上A[k - 1] < A[k + 1]，那么交换A[k]，A[k + 1]后A[k - 1] < A[k] > A[k + 1]也成立
• 如果实际上A[k] > A[k + 1]，但他们的关系应该是A[k] < A[k + 1]。根据reorder的结果我们可以得知A[k - 1] >A[k]，那么实际上A[k - 1] > A[k + 1]，那么交换A[k]，A[k + 1]后A[k - 1] > A[k] < A[k + 1]也成立

代码如下：

	public class ReorderArray {
	public void reorderSortedArray(int[] arr) {
	if (arr == null)
	return;
	int len = arr.length;
	for (int i = 1; i <= (len - 1) / 2; i += 2) {
	if (len % 2 == 0)
	swap(arr, i, len - 1 - i);
	else
	swap(arr, i, len - i);
	}
	}
	public void reorderArray(int[] arr) {
	if (arr == null)
	return;
	int len = arr.length;
	for (int i = 0; i < len - 1; i++) {
	if (i % 2 == 0 && arr[i] > arr[i + 1])
	swap(arr, i, i + 1);
	if (i % 2 == 1 && arr[i] < arr[i + 1])
	swap(arr, i, i + 1);
	}
	}
	private void swap(int[] arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
	}
	private boolean isReordered(int[] arr) {
	int len = arr.length;
	for (int i = 0; i < len - 1; i++) {
	if (i % 2 == 0 && arr[i] > arr[i + 1])
	return false;
	if (i % 2 == 1 && arr[i] < arr[i + 1])
	return false;
	}
	return true;
	}
	public static void main(String[] args) {
	test1();
	test2();
	test3();
	test4();
	test5();
	}
	// test cases
	private static void test1() {
	int[] arr = {1,2,3,4,5,6,7,8,9};
	ReorderArray r = new ReorderArray();
	r.reorderSortedArray(arr);
	if (r.isReordered(arr))
	System.out.println("Test case 1 passed!");
	else
	System.out.println("Test case 1 failed!");
	}
	private static void test2() {
	int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
	ReorderArray r = new ReorderArray();
	r.reorderSortedArray(arr);
	if (r.isReordered(arr))
	System.out.println("Test case 2 passed!");
	else
	System.out.println("Test case 2 failed!");
	}
	private static void test3() {
	int[] arr = {3,5,34,6,23,45,12,0,1};
	ReorderArray r = new ReorderArray();
	r.reorderArray(arr);
	if (r.isReordered(arr))
	System.out.println("Test case 3 passed!");
	else
	System.out.println("Test case 3 failed!");
	}
	private static void test4() {
	int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
	ReorderArray r = new ReorderArray();
	r.reorderArray(arr);
	if (r.isReordered(arr))
	System.out.println("Test case 4 passed!");
	else
	System.out.println("Test case 4 failed!");
	}
	private static void test5() {
	int[] arr = new int[10000];
	int len = arr.length;
	for (int i = 0; i < len; i++)
	arr[i] = (int)(Math.random() * len);
	ReorderArray r = new ReorderArray();
	r.reorderArray(arr);
	if (r.isReordered(arr))
	System.out.println("Test case 5 passed!");
	else
	System.out.println("Test case 5 failed!");
	}
	}

view raw reorder array.java hosted with ❤ by GitHub