資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中查詢陣列中所有消失的數字
假設我們有一個包含 n 個元素的陣列。一些元素出現兩次，另一些元素出現一次。元素的範圍是 1 <= A[i] <= n。我們必須找到陣列中不存在的那些元素。約束條件是我們必須在不使用額外空間的情況下解決此問題，並且時間複雜度為 O(n)。
因此，如果陣列為 [4, 3, 2, 7, 8, 2, 3, 1]，則結果將為 [5, 6]
為了解決這個問題，我們將遵循以下步驟：
- 設 n 為陣列的大小
- 對於 i 從 0 到 n – 1
- x := |A[i]| - 1
- 如果 A[x] > 0，則 A[x] := - A[x]
- 定義答案為一個數組
- 對於 i 從 0 到 n – 1
- 如果 A[i] > 0，則將 i + 1 新增到答案中
- 返回答案
示例
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]";
}
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& v) {
int n = v.size();
for(int i = 0;i < n; i++){
int x = abs(v[i]) - 1;
if(v[x] > 0) v[x] = -v[x];
}
vector <int> ans;
for(int i = 0; i < n; i++){
if(v[i]>0)ans.push_back(i+1);
}
return ans;
}
};
main(){
Solution ob;
vector<int> v{4,3,2,7,8,2,3,5};
print_vector(ob.findDisappearedNumbers(v));
}輸入
[4,3,2,7,8,2,3,5]
輸出
[1, 6, ]
更新於： 2020-04-28
371 次瀏覽
廣告