ধরুন আমাদের n উপাদানের একটি অ্যারে আছে। কিছু উপাদান দুইবার প্রদর্শিত হয় এবং অন্যগুলি একবার উপস্থিত হয়। উপাদানগুলি 1 রেঞ্জে রয়েছে <=A[i] <=n। আমাদের সেই উপাদানগুলো খুঁজে বের করতে হবে যেগুলো অ্যারেতে নেই। প্রতিবন্ধকতা হল অতিরিক্ত স্থান ব্যবহার না করেই আমাদের এই সমস্যার সমাধান করতে হবে, এবং সময় হবে O(n)।
সুতরাং যদি অ্যারে হয় [4, 3, 2, 7, 8, 2, 3, 1], তাহলে ফলাফল হবে [5, 6]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- আলো n হল অ্যারের আকার
- আমি 0 থেকে n – 1
- পরিসরে
- x :=|A[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, ]
