1、题目描述
找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
题目示例：
- 输入：[2, 3, 1, 0, 2, 5, 3]
- 输出：2 或 3
1.1 方法一：排序
先对数组进行排序
此时从头到尾扫一遍数组就可以了
时间复杂度 O ( l o g 2 n ) O(log_2n) O(log2n)
代码示例：
int repeatNum(vector<int>& v){
if(v.empty()) return -1;
int len = v.size();
sort(v.begin(), v.end());
for(int i = 1; i < len; i++){
if(v[i] == v[i-1]){
return v[i];
}
}
return -1;
}
1.2 方法二：哈希表
- 从头到尾扫一遍数组
- 每扫到一个数字，判断哈希表里是否包含了该数字
- 如果还没有，就把它加入哈希表中
- 如果已经存在该数字，就找到了一个重复的数字。
时间复杂度 O ( n ) O(n) O(n) 、空间复杂度 O ( n ) O(n) O(n) ，提高时间效率是以创建一个 O ( n ) O(n) O(n) 的哈希表为代价的。
代码示例：
int repeatNum(vector<int>& v){
if(v.empty()) return -1;
map<int, int> m;
for(int i = 0; i < v.size(); i++){
if(m[v[i]]) return v[i];
else m[v[i]]++;
}
return -1;
}
1.3 方法三：数组位置交换
- 从头到尾扫描数组
- 当扫描的数组下标为 i 时，判断i这个位置的数字
(m)是否等于 i 本身 - 若是则扫描下一个数字
- 若不是则判断 m 和 下标为 m 的数字是否相同
(v[i] == v[v[i]]) - 若相同则返回，循环结束
- 若不同则把第 i 个数字
(m)和 第m个数字交换 - 然后重复这个过程，直至循环结束
时间复杂度为 O ( n ) O(n) O(n) ，空间复杂度为 O ( 1 ) O(1) O(1)
代码示例：
int repeatNum(vector<int>& v){
if(v.empty()) return -1;
for(int i = 0; i < v.size(); ++i){
if(v[i] < 0 || v[i] > v.size()-1) // 数字必须在 0 ~ n-1 之间
return -1;
}
for(int i = 0; i < v.size(); ++i){
while(v[i] != i){
if(v[i] == v[v[i]]) return v[i];
swap(v[i], v[v[i]]);
}
}
return false;
}
2、题目升级
长度为 n+1 的数组，所有的数都在 1 ~ n 的范围内，因此数组中至少有一个数字是重复的。找出数组中 任意一个 重复的数字，但 不能修改输入的数组。
题目示例：
- 输入：[2, 3, 5, 4, 3, 2, 6, 7]
- 输出：2 或 3
2.1 方法一：哈希表
方法同上：
int repeatNum(vector<int>& v){
if(v.empty()) return -1;
map<int, int> m;
for(int i = 0; i < v.size(); i++){
if(m[v[i]]) return v[i];
else m[v[i]]++;
}
return -1;
}
2.2 方法二：辅助数组
- 创建一个长度为 n+1 的辅助数组，然后逐一的把原数组的每个数字复制到辅助数组中
- 若原数组中 被复制的数字 是 m，则把它复制到辅助数组中下标为 m 的位置
时间复杂度为 O ( n ) O(n) O(n) ，空间复杂度为 O ( n ) O(n) O(n)
代码示例：
int repeatNum(vector<int>& v){
int len = v.size();
vector<int> v1(len);
for(int i = 0; i < len; ++i){
if(v1[v[i]]) return v1[v[i]];
else v1[v[i]] = v[i];
}
return -1;
}
2.3 方法三：二分查找
将 1 ~ n 的数字从中间的数字 分成两部分，即分成 1 ~ m 和 m+1 ~ n
- 若 1 ~ m 的数字，在整个数组上的数目超过 m，即超过该区间的长度，那么这一半的区间里一定包含重复的数字
- 否则，另一半 m+1 ~ n 区间里一定包含重复的数字
继续把包含重复数字的区间一分为二，直到找到一个重复的数字
时间复杂度为 O ( n l o g n ) O(nlog_n) O(nlogn)，空间复杂度为 O ( 1 ) O(1) O(1)
代码示例：
int countRange(vector<int>& v, int sz, int start, int end){
if(v.empty()) return 0;
int count = 0;
for(int i = 0; i < sz; ++i){
if(v[i] >= start && v[i] <= end){
++count;
}
}
return count;
}
int getrepeat(vector<int>& v){
if(v.empty()) return -1;
int sz = v.size();
int start = 1, end = sz-1;
while(end >= start){
int mid = start + ((end-start)>>1);
int count = countRange(v, sz, start, mid);
if(end == start){
if(count > 1) return start;
else break;
}
if(count > (mid - start + 1)) end = mid;
else start = mid + 1;
}
return -1;
}
测试代码:
bool duplicate(vector<int>& v, int **res){
if(v.empty()) return false;
for(int i = 0; i < v.size(); ++i){
if(v[i] < 0 || v[i] > v.size()-1)
return false;
}
for(int i = 0; i < v.size(); ++i){
while(v[i] != i){
if(v[i] == v[v[i]]) {
*res = &v[i];
return true;
}
swap(v[i], v[v[i]]);
}
}
return false;
}
int main(){
int arr[] = {2, 3, 5, 4, 3, 2, 6, 7};
vector<int> v(arr, arr+8); // 这种赋值方式不会导致vector自动扩展内部大小
int* res = nullptr;
if(duplicate(v, &res)) cout << *res << endl;
else cout << '0' << endl;
//cout << repeatNum(v) << endl;
return 0;
}
到此这篇关于关于C++数组中重复的数字的文章就介绍到这了,更多相关C++数组中重复数字内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
注：文章转自微信公众号：Coder梁（ID：Coder_LT）
