C++-এ মেজরিটি এলিমেন্ট II

একটি পূর্ণসংখ্যার অ্যারে দেওয়া থাকলে, আমাদের সেই উপাদানগুলো খুঁজে বের করতে হবে যা n/3 এর ফ্লোর ভ্যালু এর চেয়ে বেশি বার আসে। এখানে n হলো অ্যারেটির আকার।

উদাহরণস্বরূপ, ইনপুট [1,1,1,3,3,2,2,2] হলে আউটপুট হবে [1,2]।

সমাধানের ধাপসমূহ

• first := 0, second := 1, cnt1 := 0, cnt2 := 0, n := nums.size()।
• 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--।
• cnt1 = 0, cnt2 = 0 রিসেট করুন।
• আবার i = 0 থেকে n-1 পর্যন্ত লুপ করে実际 গণনা করুন।
• ফলাফল ভেক্টর ret তৈরি করুন।
• যদি cnt1 > n/3 হয়, first যোগ করুন।
• যদি cnt2 > n/3 হয়, second যোগ করুন।
• ret রিটার্ন করুন।

C++ উদাহরণ

#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 << "]" << endl;
}

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int first = 0, second = 1;
        int cnt1 = 0, 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;
    }
};

int 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, ]