找出数组中重复的数字 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
限制:
2 <= n <= 100000
方法一(hash计数):
空间复杂度为O(n),时间复杂度为O(n),典型的以空间换时间的策略
class Solution {
public:
int findRepeatNumber(vector<int>& a) {
int n = a.size();
int hash[n];
for (int i=0; i<n; ++i) hash[i] = 0;
for (int i=0; i<n; ++i) hash[a[i]] ++;
for (int i=0; i<n; ++i) {
if (hash[i] > 1) return i;
}
return -1;
}
};
方法二 .排序,比较相邻元素
空间复杂度为O(1),时间复杂度为O(nlogn)
class Solution {
public:
int findRepeatNumber(vector<int>& a) {
sort(a.begin(), a.end());
for (int i=1; i<a.size(); ++i) {
if (a[i] == a[i-1]) return a[i];
}
return -1;
}
};
方法三 .抽屉原理
利用题目已知的条件,数组长度为n,且数组内所有元素的范围为0~n-1。利用这个特性,将值为x的元素放置在a[x]中,在放置的过程中,如果a[x]==a[a[x]] (a[x]作为索引),说明有重复。否则,交换a[x]与a[a[x]]。
class Solution {
public:
int findRepeatNumber(vector<int>& a) {
int n = a.size();
for (int i=0; i<n; ++i) {
while (i != a[i]) {
if (a[i] == a[a[i]]) return a[i];
swap(a[i], a[a[i]]);
}
}
return -1;
}
};