题目
找出数组中重复的数字
数组中数字都在0~n之间,其中有些数字是重复的，但不知道谁重复，可能有1到多个重复的数字，请找出任意一个。
题解
解法1：
- 排序
- 遍历判断相邻相等性
时间复杂度 Onlogn,空间复杂度 原数组排序 O1；
解法2：
- 哈希表
- 判断是否存在
时间复杂度On,空间复杂度On 需要大小为n的哈希表
解法3：
- 归正下标
- 遍历数组，将数字放到对应的下标处，如果放置前该位置已经存在对应的数字则该数字即为重复数字。
public int findRepeatNumber(int[] nums) {
if(nums==null) return -1;
for(int i=0;i<nums.length;i++){
int val = nums[i];
while(val!=i){
if(nums[val]==val){
return val;
}
int temp = nums[val];
nums[val] = val;
val = temp;
}
}
return -1;
}
源码: 剑指offer4J
