面试题03. 数组中重复的数字
找出数组中重复的数字 在一个长度为 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;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读