数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律研究以 O(n) 的时间复杂度和 O(1) 的额外空间在 C++ 中寻找数组中的重复元素
假设我们有一份包含 0 到 n-1 的数字清单。一个数字可以尽可能地重复多次。我们不得占用任何额外空间，但是必须找到这些重复的数字。如果 n = 7，并且清单类似于 [5, 2, 3, 5, 1, 6, 2, 3, 4, 5]。答案将是 5、2、3。
为了解决这个问题，我们必须遵循这些步骤 −
- 对列表中的各个元素 e 执行以下步骤 −
- sign := A[|e|]
- 如果 sign 为正，则改成负
- 否则，就是重复。
示例
#include<iostream>
#include<cmath>
using namespace std;
void findDuplicates(int arr[], int size) {
for (int i = 0; i < size; i++) {
if (arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] *= -1;
else
cout << abs(arr[i]) << " ";
}
}
int main() {
int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1};
int n = sizeof(arr)/sizeof(arr[0]);
findDuplicates(arr, n);
}输出
5 2 3 1
更新时间：2019 年 12 月 19 日
89 次浏览
广告