1287. Element Appearing More Than 25% In Sorted Array

O(logn) time O(1) space

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = size(arr);
        for (auto p : {.25, .5, .75}) { // 分别测试每个quartile位置的数，超过25%的数一定能被capture
            int i = n * p;
            auto [b, e] = equal_range(begin(arr), end(arr), arr[i]);
            if (e - b > n / 4) return arr[i];
        }
        return -1;
    }
};

O(n) time O(1) space

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size(), mx = n * .25;
        for (int i = 0; i < n;) {
            int j = i;
            while (arr[j] == arr[i]) {
                if (++j - i > mx) return arr[i]; // 一旦找到则提前返回
            }
            i = j;
        }
        return -1;
    }
};