剑指offer之数组中重复的数字
题目描述
在一个长度为n的数组里所有数字都在0到n-1的范围内，
数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。
请找出数组中任意一个重复的数字。
解题思路
要求时间复杂度O(N)，空间复杂度O(1)。
对于这种数组元素在[0,n-1]范围内的问题，可以将值为i的元素调整到第i个位置上进行求解。
以(2,3,1,0,2,5)为例，遍历到位置4时，该位置上数为2，但是第二个位置上已经有一个2的值了。
因此，可以知道2重复。
解题代码
public static void main(String[] args) {
int[] nums = {2, 3, 1, 0, 2, 5};
int[] duplication = new int[1];
duplicate(nums, 6, duplication);
System.out.println(duplication[0]);
}
public static boolean duplicate(int[] nums, int length, int[] duplication) {
if (nums == null || length <= 0) {
return false;
}
for (int i = 0; i < length; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
duplication[0] = nums[i];
return true;
}
swap(nums, i, nums[i]);
}
}
return false;
}
public static void swap(int[] nums, int i, int j) {
// 换位
// a = a ^ b
// b = a ^ b
// a = a ^ b
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}