摘要：
常见判重方法。
题目
找出数组中重复的数字。
在一个长度为 $n$ 的数组 $nums$ 里的所有数字都在 $0～n-1$ 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：
2 或 3
限制：
$ 2 <= n <= 100000 $
本题考查判重方法。
方法一：计数数组
维护一个计数数组，根据题意长度为 n 的数组每个数范围在 $[0, n-1]$ ，那么数组长度可以设置成大于等于 n-1 。
遍历数组，依次向计数数组中插入数字。对于当前数字 x , 在下标为 x 的位置数字增加 1 。如果当前值大于 1，则出现重复。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
vector<int> cnt;
int len;
int findRepeatNumber(vector<int>& nums) {
len = nums.size();
cnt = vector<int>(len + 10);
for (int n : nums) {
if (++cnt[n] > 1) return n;
}
return 0;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
int[] cnt;
int len;
public int findRepeatNumber(int[] nums) {
len = nums.length;
cnt = new int[len + 10];
for (int n : nums) {
if (++cnt[n] > 1) return n;
}
return 0;
}
}
|
方法二：哈希集合
向哈希集合中插入每个数，如果插入失败，则出现重复。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
unordered_set<int> set;
for (int n : nums) {
if (!set.insert(n).second) {
return n;
}
}
return 0;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums) {
if (!set.add(n)) return n;
}
return 0;
}
}
|
方法三：哈希表
维护一个哈希表，依次将每个数插入，但是，在插入之前先检查是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
unordered_map<int, bool> hash;
for (int n : nums) {
if (hash[n]) return n;
else hash[n] = true;
}
return 0;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public int findRepeatNumber(int[] nums) {
Map<Integer, Boolean> hash = new HashMap<>();
for (int n : nums) {
if (hash.get(n) == null) {
hash.put(n, true);
} else if (hash.get(n)) {
return n;
} else {
hash.put(n, true);
}
}
return 0;
}
}
|