文章目录- 找出数组中重复的数字
- 方法一 使用hashset
- 方法二 巧妙采用原地置换法
- 方法一 使用hashset
- 方法二 巧妙采用原地置换法
找出数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
限制：
2 <= n <= 100000
这道题给你你会怎么做呢？
方法一 使用hashset
代码语言：javascript复制class Solution {
public int findRepeatNumber(int[] nums) {
Set hashMap = new HashSet<>();
for (int i = 0; i < nums.length; i ) {
if (hashMap.contains(nums[i])) {
return nums[i];
}
hashMap.add(nums[i]);
}
return 0;
}
}hashset很简单 一个个的放入set集合中 如果有的话直接输出了
方法二 巧妙采用原地置换法
代码语言：javascript复制class Solution {
public int findRepeatNumber(int[] nums) {
int temp = 0;
for(int i=0;i<nums.length;i ){
while(i!=nums[i]) {
//交换
if(nums[i]==nums[nums[i]]) {
return nums[i];
}
temp= nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
}
}
return temp;
}
}原地置换是什么意思呢？
如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回ture
看给的示例 [2, 3, 1, 0, 2, 5, 3]
第一个是2 发现下标为2的元素和2不相等 就和下标为2的元素交换 变成[1, 3, 2, 0, 2, 5, 3]
第二个是3 发现下标为3的元素和3不相等 就和下标为3的元素交换 变成[1, 0, 2, 3, 2, 5, 3]
第三个是2 发现下标为2的元素正好和2相等 就跳过
第四个是3 发现下标为3的元素正好和3相等 就跳过
第五个是2 发现下标为2的元素和2相等 说明重复了 就直接输出返回
