Majority Element II ใน C++: หาองค์ประกอบที่ปรากฏมากกว่า n/3 ครั้ง

โจทย์

กำหนดอาร์เรย์จำนวนเต็ม ให้หาองค์ประกอบที่ปรากฏมากกว่า floor(n/3) ครั้ง โดยที่ n คือขนาดของอาร์เรย์

ตัวอย่าง: หากอินพุตคือ [1,1,1,3,3,2,2,2] ผลลัพธ์จะเป็น [1,2]

แนวคิดการแก้ปัญหา (Boyer-Moore Voting Algorithm ขยายรูปแบบ)

เนื่องจากองค์ประกอบที่ปรากฏมากกว่า n/3 ครั้ง สูงสุดมีได้ 2 ตัว เราสามารถใช้ตัวนับ 2 คู่เพื่อติดตามผู้สมัครใจ (candidates) ได้

ขั้นตอน

1. กำหนด first = 0, second = 1, cnt1 = 0, cnt2 = 0, n = nums.size()
2. ลูปผ่านอาร์เรย์ 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--
3. รีเซ็ต cnt1 = 0, cnt2 = 0 แล้วลูปนับจริงอีกครั้ง
4. ถ้า cnt1 > n/3 ใส่ first ลงผลลัพธ์
5. ถ้า cnt2 > n/3 ใส่ second ลงผลลัพธ์

ตัวอย่างโค้ด 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));
    return 0;
}

อินพุต / เอาต์พุต

Input: [1,1,1,3,3,2,2,2]

Output: [1, 2]

ความซับซ้อน

• Time: O(n) - ผ่านอาร์เรย์ 2 รอบ
• Space: O(1) - ใช้พื้นที่คงที่