一个公司的Java面试题

因为数组元素和下标有对应关系,所以可以这样排序:

		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == i + min) { //在其对应位置
				continue;
			}
			if (arr[i] - min > arr.length) { //越界及时退出
				break;
			}
			while (arr[i] != arr[arr[i] - min]) { //一直交换直到找到对应的元素,或找不到(要交换的值重复时找不到)
				int t = arr[arr[i] - min];
				arr[arr[i] - min] = arr[i];
				arr[i] = t;
			}
		}

说明:min是先遍历一遍取得的最小值,这样排序好之后,再遍历一遍判断是否构成连续。
虽然是双重循环,实际时间复杂度为O(n),这样即可三次遍历并在O(1)的空间复杂度里解决问题