Leetcode 1287

题目要求

非递减数组arr，该数组中恰好有一个数的出现次数大于元素总数的25%，找出这个元素

核心算法和原理

• 由于数组有序，可以直接检查下面三个点的元素的出现次数：

• 令m = ⌊n / 4⌋，检查arr[m], arr[2m + 1], arr[3m + 2]（如果对应索引的元素是存在的）

• 可反证：如果这三个点的元素出现次数都≤m，则不可能有元素的出现次数>m

• 元素个数≤3时，直接返回arr[0]

• 否则，用二分找到前两个元素的最早出现位置p，并判断arr[p] == arr[p + m]，为true直接返回；如果两个都不满足则返回arr[3m + 2]

代码

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size();
        if (n <= 3) {
            return arr[0];
        }
        int left, right, mid;
        int target[2] = {arr[n / 4], arr[2 * (n / 4) + 1]};
        for (int t : target) {
            left = 0;
            right = n;
            while (left < right) {
                mid = (left + right) / 2;
                if (t <= arr[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            // cout << left << endl;
            if (arr[left] == arr[left + n / 4]) {
                return arr[left];
            }
        }
        return arr[3 * (n / 4) + 2];
    }
};