資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在O(n)時間和O(1)額外空間中尋找重複項- C++中的集合1
假設我們有一個從0到n-1的數字列表。數字可以儘可能重複多次。我們必須在不佔用任何額外空間的情況下找出重複的數字。如果n = 7，並且列表像[5, 2, 3, 5, 1, 6, 2, 3, 4, 5]。答案將是5、2、3。
要解決此問題，我們必須遵循以下步驟−
對列表中的每個元素e，執行以下步驟−
- 符號:= A[e的絕對值]
- 如果符號為正，則將其變為負
- 否則，重複。
示例
#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-11-01
239 次瀏覽
廣告