สมมติว่าเรามีอาร์เรย์ขององค์ประกอบ 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, ]
