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