Phần tử xuất hiện > 25% trong mảng đã sắp xếp C++

Cho mảng đã sắp xếp, tìm phần tử xuất hiện > 25% độ dài mảng. Mảng đã sắp xếp nên các phần tử giống nhau liền kề.

Thuật toán

Vì mảng đã sắp xếp, phần tử xuất hiện > 25% sẽ xuất hiện tại vị trí i, i + n/4, i + n/2, i + 3n/4. Chỉ cần kiểm tra các vị trí n/4, n/2, 3n/4.

Cách đơn giản: Dùng unordered_map đếm tần suất (O(n) time, O(n) space).

Chương trình mẫu (Hash Map)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size();
        int threshold = n / 4;
        unordered_map<int, int> freq;
        
        for (int x : arr) {
            if (++freq[x] > threshold)
                return x;
        }
        return -1; // Không tìm thấy (theo đề bài luôn có)
    }
};

int main() {
    Solution ob;
    vector<int> c = {1, 2, 4, 4, 4, 4, 5, 5, 6, 6, 7, 7};
    cout << ob.findSpecialInteger(c);
    return 0;
}

Kết quả

4

Tối ưu cho mảng sorted (O(1) space):

int findSpecialInteger(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i + n/4 < n; i++) {
        if (arr[i] == arr[i + n/4])
            return arr[i];
    }
    return -1;
}

Vì mảng sorted, nếu arr[i] == arr[i+n/4] → phần tử đó xuất hiện ít nhất n/4+1 lần (> 25%).

Độ phức tạp: Hash map O(n) time/space. Sorted array trick O(n) time, O(1) space.