मान लीजिए कि हमारे पास एक पूर्णांक सरणी है; हमें उन तत्वों को खोजना है जो n/3 के तल से अधिक दिखाई देते हैं। यहाँ n सरणी का आकार है।
तो अगर इनपुट [1,1,1,3,3,2,2,2] जैसा है, तो परिणाम [1,2]
होंगे।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
पहला:=0, दूसरा:=1, cnt1:=0, cnt2:=0, n:=सरणी संख्याओं का आकार
-
मेरे लिए 0 से लेकर n - 1 के आकार तक
-
एक्स:=अंक [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 की सीमा में
-
यदि nums[i] =पहले, फिर cnt1 को 1 से बढ़ाएँ, अन्यथा जब nums[i] दूसरा हो, तो cnt2 को 1 से बढ़ाएँ
-
-
रिट नामक एक सरणी बनाएं
-
अगर cnt1> n / 3, तो पहले रिट में डालें
-
अगर cnt2> n / 3, फिर रिट में दूसरा डालें
-
वापसी सेवानिवृत्त।
उदाहरण(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, ]