資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告