Phần tử đa số II trong C++

Cho một mảng số nguyên, ta cần tìm các phần tử xuất hiện nhiều hơn ⌊n/3⌋ lần, trong đó n là kích thước mảng.

Ví dụ: với đầu vào [1,1,1,3,3,2,2,2], kết quả sẽ là [1,2].

Thuật toán giải quyết

Áp dụng thuật toán Boyer-Moore mở rộng cho ngưỡng n/3. Ta duy trì hai ứng viên tiềm năng và bộ đếm tương ứng:

1. Khởi tạo: first = 0, second = 1, cnt1 = 0, cnt2 = 0, n = nums.size().
2. Duyệt mảng lần đầu để tìm hai ứng viên:
• Nếu phần tử hiện tại bằng first → tăng cnt1.
• Ngược lại nếu bằng second → tăng cnt2.
• Ngược lại nếu cnt1 == 0 → gán first = x, cnt1 = 1.
• Ngược lại nếu cnt2 == 0 → gán second = x, cnt2 = 1.
• Ngược lại → giảm cả cnt1 và cnt2 xuống 1.
3. Đặt lại cnt1 = 0, cnt2 = 0.
4. Duyệt mảng lần hai để đếm chính xác số lần xuất hiện của hai ứng viên.
5. Tạo mảng kết quả ret.
6. Nếu cnt1 > n/3 → thêm first vào ret.
7. Nếu cnt2 > n/3 → thêm second vào ret.
8. Trả về ret.

Ví dụ minh họa (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, 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));
}

Đầu vào

[1,1,1,3,3,2,2,2]

Đầu ra

[2, 1, ]