原题:剑指 Offer 03. 数组中重复的数字
class Solution { /* public int findRepeatNumber(int[] nums) { Set<Integer> set = new HashSet<>(); for(int n : nums){ if(!set.add(n)){ return n; } } return 0; } */ public int findRepeatNumber(int[] nums) { int i = 0; while(i < nums.length){//注意:这里不能用for,因为不是所有情况i都+1,而是当第一个if成立时,i才+1。 if(nums[i] == i) { i++; continue; } if(nums[nums[i]] == nums[i]) return nums[i]; int temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } return -1; } }
由于题干中已知数组中的数都在0-n-1范围,利用这点可以在原地解决该题。
遍历中,第一次遇到数字 x 时,将其交换至索引 x 处;而当第二次遇到数字 x 时,一定有 nums[x] = x ,此时即可得到一组重复数字。
理解本题的测试用例:2,3,1,1
if(set.contains(n)){ return n; } else{ set.add(n); }
这段代码这样写更简洁:
if(!set.add(n)){ return n; }
set.add(n)返回值是boolean,如果n已经在set中存在,返回false。