ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে আছে; আমাদের সেই উপাদানগুলি খুঁজে বের করতে হবে যেগুলি n/3 এর ফ্লোরের চেয়ে বেশি প্রদর্শিত হয়। এখানে n হল অ্যারের আকার।
সুতরাং ইনপুট যদি [1,1,1,3,3,2,2,2] এর মত হয়, তাহলে ফলাফল হবে [1,2]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
প্রথম :=0, দ্বিতীয় :=1, cnt1 :=0, cnt2 :=0, n :=অ্যারের সংখ্যার আকার
-
আমি 0 থেকে n – 1
এর পরিসরে-
x :=সংখ্যা[i]
-
যদি x প্রথম হয়, তাহলে cnt 1 দ্বারা বাড়ান,
-
অন্যথায় যখন x দ্বিতীয় হয়, তখন cnt2 বাড়ান 1
-
অন্যথায় যখন cnt1 0 হয়, তখন প্রথমে x এবং cnt1 :=1
হিসেবে সেট করুন -
অন্যথায় যখন cnt2 0 হয়, তখন x এবং cnt2 হিসাবে দ্বিতীয় সেট করুন :=1
-
অন্যথায় cnt1 এবং cnt2 1 দ্বারা হ্রাস করুন
-
-
cnt1 :=0 এবং cnt2 :=0
সেট করুন -
0 থেকে n – 1
রেঞ্জের i জন্য-
যদি nums[i] =প্রথমে, তারপর cnt1 1 দ্বারা বাড়ান, অন্যথায় যখন nums[i] দ্বিতীয় হয়, তখন cnt2 1 দ্বারা বাড়ান
-
-
ret
নামে একটি অ্যারে তৈরি করুন -
যদি cnt1> n / 3 হয়, তাহলে প্রথমে ret এ সন্নিবেশ করুন
-
যদি cnt2> n / 3 হয়, তাহলে ret
-এ দ্বিতীয়টি সন্নিবেশ করান -
রিটার্ন রিটার্ন।
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int first = 0;
int second = 1;
int cnt1 = 0;
int cnt2 = 0;
int n = nums.size();
for(int i = 0; i < n; i++){
int x = nums[i];
if(x == first){
cnt1++;
}
else if(x == second){
cnt2++;
}
else if(cnt1 == 0){
first = x;
cnt1 = 1;
}
else if(cnt2 == 0){
second = x;
cnt2 = 1;
} else {
cnt1--;
cnt2--;
}
}
cnt1 = 0;
cnt2 = 0;
for(int i = 0; i < n; i++){
if(nums[i] == first)cnt1++;
else if(nums[i] == second)cnt2++;
}
vector <int> ret;
if(cnt1 > n / 3)ret.push_back(first);
if(cnt2 > n / 3)ret.push_back(second);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1, 1, 1, 3, 3, 2, 2, 2};
print_vector(ob.majorityElement(v));
} ইনপুট
[1,1,1,3,3,2,2,2]
আউটপুট
[2, 1, ]
