এই সমস্যায় একটি অ্যারে দেওয়া থাকলে, যেখানে এলিমেন্টগুলো 1 থেকে n (অ্যারে সাইজ) এর মধ্যে, এবং কিছু এলিমেন্ট দুবার আসে, কিছু একবার। যেসব এলিমেন্ট দুবার আসে সেগুলো বের করতে হবে O(n) টাইম এবং O(1) এক্সট্রা স্পেসে।
উদাহরণ: [4,3,2,7,8,2,3,1] -> আউটপুট [2,3]।
সমাধানের পদ্ধতি (Index Marking - Negative Marking)
- প্রতিটি এলিমেন্ট
x = abs(nums[i])এর জন্য, ইন্ডেক্সx-1-এ যান। - যদি
nums[x-1]ইতিমধ্যে নেগেটিভ হয়, তবেxডুপ্লিকেট। - অন্যথায়
nums[x-1] *= -1করে চিহ্নিত করুন।
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
void printVec(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) cout << v[i] << (i+1==v.size()?"":", ");
cout << "]" << endl;
}
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ans;
for (int i = 0; i < nums.size(); i++) {
int x = abs(nums[i]);
if (nums[x - 1] < 0)
ans.push_back(x);
else
nums[x - 1] *= -1;
}
return ans;
}
};
int main() {
Solution ob;
vector<int> v = {4, 3, 2, 7, 8, 2, 3, 1};
printVec(ob.findDuplicates(v));
return 0;
}
ইনপুট
[4,3,2,7,8,2,3,1]
আউটপুট
[2, 3]
