剑指offer-50、数组中重复的数字 _

思路及解答借用Set⾸先可能想到的做法就是借助 set 如果元素不存在 set 中就将元素添加进去如果 set中包含该元素就返回该元素即可。如果⼀直都没有重复的那么最后返回 -1 。javapublic class Solution { public int duplicate(int[] numbers) { if (numbers ! null) { SetInteger set new HashSet(); for (int i 0; i numbers.length; i) { if (set.contains(numbers[i])) { return numbers[i]; } else { set.add(numbers[i]); } } } return -1; } }时间复杂度O(n) 最差的情况可能遍历完所有的元素空间复杂度 O(n) 最⼤需 要set ⼤⼩为 n借助数组可以直接借助数组因为所有数字都在 0 到 n-1 的范围内⽤⼀个⼤⼩为 n 的数组就可以对所有的数字进⾏统计个数如果个数超过 1 那么肯定是重复的数字如果没有重复的数字则返回 -1 javapublic class Solution { public int duplicate(int[] numbers) { if (numbers ! null) { int[] nums new int[numbers.length]; for (int i 0; i numbers.length; i) { if (nums[numbers[i]] 1) { return numbers[i]; } else { nums[numbers[i]] 1; } } } return -1; } }同样这种做法的时间复杂度和空间复杂度都是 O(n) ,并没有优化太多。那么有没有空间复杂度为O(1) 的做法呢操作原数组最优不借助额外的空间那么就只能操作原数组了。如果没有重复的情况那么这些数字排序后数字i 和数组下标i 应该是⼀⼀对应的。不会出现多个数字i 的情况。基于这个原则在遍历数组的时候将元素 i 调整到下标 i 的位置如果下标i的位置已经有元素那么说明冲突了这个元素肯定是重复的否则继续调整后⾯的。如果没有发现重复的数字就返回 -1 。javapublic class Solution { public int duplicate(int[] numbers) { int i 0; while(i numbers.length) { if(numbers[i] i) { i; continue; } if(numbers[numbers[i]] numbers[i]) return numbers[i]; int tmp numbers[i]; numbers[i] numbers[tmp]; numbers[tmp] tmp; } return -1; } }但是上⾯的做法不适合求解多个重复数字的例⼦因为调换的时候很容易将后⾯的数字换到前⾯去就会导致求解出来不是第⼀个重复的数字可以⽤来求解任意的重复数字可能是第23... 或者其他的重复数字。譬如 [6,3,2,0,2,5,0] 正确的解应该是 2 但是由于第⼀次把 6 和最后的0 调换了位置就会导致求解出来的值为 0 。