剑指 Offer 03.数组中重复的数字

题目描述

原题
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
1
输入:
2
[2, 3, 1, 0, 2, 5, 3]
3
输出:23
Copied!
限制:
2 <= n <= 100000

题解

暴力求解

1
class Solution {
2
public int findRepeatNumber(int[] nums) {
3
for(int i = 0;i<nums.length-1;i++){
4
for(int j = i+1;j<nums.length;j++){
5
if(nums[i]==nums[j]){
6
return nums[i];
7
}
8
}
9
}
10
return -1;
11
}
12
}
Copied!

哈希查找

1
class Solution {
2
public int findRepeatNumber(int[] nums) {
3
Set<Integer> set = new HashSet<>();
4
for(int num:nums){
5
if(!set.add(num)){
6
return num;
7
}
8
}
9
return -1;
10
}
11
}
Copied!

原地交换

1
class Solution {
2
public int findRepeatNumber(int[] nums) {
3
//长度为n的数组 索引范围是0~n-1
4
//根据题目中所有数字都在0~n-1之间
5
//我们可以在0的位置存0 1的位置存1 n的位置存n
6
//存入的时候判断该位置 索引是否与值相等 如果已经相等说明重复了
7
int length = nums.length;
8
int i = 0;
9
//遍历
10
while(i<length){
11
//索引与值比较 不相等 则存入当前值
12
if(nums[i]!=i){
13
//查询值作为索引对应位置的值 是否与索引相同
14
if(nums[nums[i]]==nums[i]){
15
return nums[i];
16
}else{
17
//不相等进行交换
18
int tmp = nums[i];
19
nums[i] = nums[tmp];
20
//注意这里不要写一定是nums[tmp]不是nums[nums[i]]
21
nums[tmp] = tmp;
22
}
23
}
24
i++;
25
}
26
return -1;
27
}
28
}
Copied!
最近更新 9mo ago