สมมติเรามี array n องค์ประกอบ บางองค์ประกต์ปรากฏ 2 ครั้ง บางอย่าง 1 ครั้ง องค์ประกอบอยู่ในช่วง 1 <= A[i] <= n เราต้องหาองค์ประกอบที่ไม่ได้ปรากฏใน array เงื่อนไขคือต้องแก้โดยไม่ใช้ extra space และ time เป็น O(n)
เช่นถ้า array คือ [4, 3, 2, 7, 8, 2, 3, 1] ผลลัพธ์จะเป็น [5, 6]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- ให้ n เป็นขนาดของ array
- for i ในช่วง 0 ถึง n - 1:
- x := |A[i]| - 1
- ถ้า A[x] > 0 แล้ว A[x] := -A[x]
- กำหนด answer เป็น array
- for i ในช่วง 0 ถึง n - 1:
- ถ้า A[i] > 0 แล้วเพิ่ม i + 1 เข้า answer
- คืนค่า answer
โปรแกรมตัวอย่าง
#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));
}
Input
[4,3,2,7,8,2,3,5]
Output
[1, 6, ]
