Cho mảng n phần tử, giá trị trong [1, n]. Một số xuất hiện 2 lần, số khác 1 lần. Tìm các số trong [1, n] không xuất hiện. Không dùng thêm không gian, O(n).
Input: [4,3,2,7,8,2,3,1] Output: [5,6]
Giải pháp: Dùng mảng đầu vào làm hash. Với mỗi phần tử x, đánh dấu vị trí |x|-1 thành âm. Các vị trí còn dương tương ứng số thiếu.
Chương trình minh họa
#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;
}
};
int main(){
Solution ob;
vector<int> v{4,3,2,7,8,2,3,5};
print_vector(ob.findDisappearedNumbers(v));
return 0;
}
Kết quả
[1, 6, ]