剑指 Offer 03. 数组中重复的数字
难度简单372
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
代码语言：javascript复制输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 方法一:
利用set集合,如每次添加的时候判重
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set=new HashSet<>();
for (int num:nums){
if (!set.contains(num)){
set.add(num);
}else {
return num;
}
}
return 0;
}
}复杂性分析
时间复杂度：O(n)
遍历数组一遍。使用哈希集合（HashSet），添加元素的时间复杂度为 O(1)，故总的时间复杂度是 O(n)
空间复杂度：O(n)。
不重复的每个元素都可能存入集合，因此占用 O(n)额外空间。
方法二: 原地置换法
- 注意:数字的范围与数组的长度相同,我们可以把数组看成哈希表
- 把数组的索引看成哈希表的kye,数组的元素看成哈希表的值val
- 把值为val的元素放在键也为val的位置上，也就是哈希表键值对的映射关系为key == val
- 如果当前数字 nums[i] 和索引 i 不相等，那么应该把 nums[i] 放在索引也为 nums[i] 的位置去，就把索引为 nums[i] 和 i 的数字对换
- 如果数组在索引为 nums[i] 位置的数在交换前就已经是 nums[i]，说明nums[i]是重复数字，返回nums[i]
- 如果交换后在 nums[i] 仍然不等于 i，要继续交换，这是使用while循环的原因
public int findRepeatNumber2(int[] nums) {
for (int i = 0; i < nums.length; i ) {
if (i == nums[i]) {
continue;
}
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
//交换
int temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
//这里的i--是为了抵消掉上面的i ，
//交换之后需要原地再比较
i--;
}
return -1;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
本文来源面相薪水编程，由javajgs_com转载发布，观点不代表Java架构师必看的立场，转载请标明来源出处
