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