Giả sử chúng ta có một mảng gồm n phần tử. Một số phần tử xuất hiện hai lần và phần tử khác xuất hiện một lần. Các phần tử nằm trong phạm vi 1 <=A [i] <=n. Chúng ta phải tìm những phần tử không có trong mảng. Hạn chế là chúng ta phải giải quyết vấn đề này mà không sử dụng thêm dung lượng và thời gian sẽ là O (n).
Vì vậy, nếu mảng là [4, 3, 2, 7, 8, 2, 3, 1], thì kết quả sẽ là [5, 6]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- đặt n là kích thước của mảng
- cho tôi trong phạm vi từ 0 đến n - 1
- x:=| A [i] | - 1
- nếu A [x]> 0, thì A [x]:=- A [x]
- xác định câu trả lời dưới dạng một mảng
- cho tôi trong phạm vi từ 0 đến n - 1
- nếu A [i]> 0, thì hãy thêm i + 1 vào câu trả lời
- trả lời câu trả lời
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
[4,3,2,7,8,2,3,5]
Đầu ra
[1, 6, ]