重排数组使得array[i]等于array[array[i]]，但只能用0(1)的额外空间_JAVA_编程开发_程序员俱乐部

题目：给定一个长度为N的数组，里面的每一个元素的值都在0到N-1之间，并且数组的元素是各不相同的。重新排列这个数组，使得array[i]的值变成array[array[i]], 但是只能使用0(1)的额外空间。


实现的代码如下：

class="java">

import java.util.Arrays;

/**
 * <pre>
 * 题目要求：重新排列一个数组，使得array[i]的值变成array[array[i]], 
 *           只能使用0(1)的额外空间。
 *           
 * 題目描述：给定一个长度为N的数组，里面的每一个元素的值都在0到N-1之间，并且数组的元素是各不相同的。重新排列
 *          这个数组，使得array[i]的值变成array[array[i]], 但是只能使用0(1)的额外空间。
 * </pre>
 * 
 * 例如:
 * 
 * {3, 2, 0, 1} ==> {1, 0, 3, 2}
 * 
 * {4, 0, 2, 1, 3} ==> {3, 4, 2, 0, 1}
 * 
 * {0, 1, 2, 3} ==> {0, 1, 2, 3}
 * 
 * ...
 * 
 * @author Eric
 * 
 */
public class RearrangeArray {

	/**
	 * 重新排列一个给定的数组，使得array[i]的值变成array[array[i]], 但是只能使用0(1)的额外空间。
	 */
	public int[] rearrange(int[] array) {

		if (null == array) {
			throw new IllegalArgumentException("数组不是为NULL.");
		}

		if (!(isArrayExpected(array.clone()))) {
			throw new IllegalArgumentException(
					"长度为N的数组，里面的每一个元素的值都在0到N-1之间，并且数组的元素是各不相同的。");
		}

		int len = array.length;

		/*
		 * 每个位置的元素都增加一个值，这个值为(array[array[i]] % N) * N
		 * 
		 * 这样做的好处是让每个元素同时拥有旧的和新的值。
		 * 
		 * oldValue = array[i] % N, newValue = array[i] / N
		 */
		for (int i = 0; i < len; i++) {
			array[i] += (array[array[i]] % len) * len;
		}

		/*
		 * 计算新的值，newValue = array[i] / N
		 */
		for (int i = 0; i < len; i++) {
			array[i] /= len;
		}
		return array;
	}

	/**
	 * 判断待处理的整形数组其所拥有的元素是否符合要求。
	 */
	private boolean isArrayExpected(int[] array) {
		Arrays.sort(array);
		/*
		 * 如果是符合要求数组，那么其排序后的结果将会是{0,1,2,3,...N-1}
		 */
		for (int i = 0; i < array.length; i++) {
			if (i != array[i]) {
				return false;
			}
		}

		return true;
	}

}

一个测试例子如下：

import java.util.Arrays;

public class Test {

	public static void main(String[] args) {
		int[] origArray = { 3, 2, 0, 1 };

		System.out.printf("原数组的内容是%s\n", Arrays.toString(origArray));
		RearrangeArray ra = new RearrangeArray();

		System.out.printf("变换后的数组内容是%s\n",
				Arrays.toString(ra.rearrange(origArray)));
	}
}

运行结果如下：

原数组的内容是[3, 2, 0, 1]
变换后的数组内容是[1, 0, 3, 2]