मान लीजिए हमारे पास n तत्वों की एक सरणी है। कुछ तत्व दो बार प्रकट होते हैं और अन्य एक बार। तत्व 1 <= A[i] <= n की सीमा में हैं। हमें उन तत्वों को ढूंढना है जो सरणी में मौजूद नहीं हैं। प्रतिबंध यह है कि हमें इस समस्या को अतिरिक्त स्थान के बिना हल करना है, और समय O(n) होगा।
इसलिए यदि सरणी [4, 3, 2, 7, 8, 2, 3, 1] है, तो परिणाम [5, 6] होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- let 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, ]
