题目描述

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

题意：给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。请你找到并返回这个整数。

算法1

(枚举) $O(n)$

因为数组已经排好序了，那么相同的数字肯定是连续出现的，我们只需要统计一下每一个连续出现的数字出现次数即可。

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

算法2

(枚举) $O(n)$

我们还可以发现，如果数字出现个数大于数组长度的四分之一，那么我们只需要判断每一个数字和其相距四分之一长度的数字是否相同即可。

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

算法3

(枚举若干个+二分) $O(logn)$

还有一种做法则是，该数字必定在arr[0],arr[gap],arr[gap * 2],arr[gap * 3]中出现了，我们只需要判断这四个数字即可，可以使用二分查找找到每一个数字首尾出现的下标。

    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size(), gap = n / 4;
        for(int i = 0 ; i < 4 ; i ++)
        {
            int val = arr[gap * i],first_idx,last_idx;
            //  二分查找大于等于val的最小的数字（第一次出现）
            int l = 0,r = n - 1;
            while(l < r)
            {
                int mid = (l + r) / 2;
                if(arr[mid] >= val) r = mid;
                else l = mid + 1;
            }
            first_idx = l;
            //  二分查找小于等于val最大的数字（最后一次出现）
            l = 0,r = n - 1;
            while(l < r)
            {
                int mid = (l + r + 1) / 2;
                if(arr[mid] <= val) l = mid;
                else r = mid - 1;
            }
            last_idx = l;
            if(last_idx - first_idx + 1 > gap)
                return val;
        }
        return 0;
    }

    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size(), gap = n / 4;
        for(int i = 0 ; i < 4 ; i ++)
        {
            int val = arr[gap * i];
            auto first_it = lower_bound(arr.begin(),arr.end(),val);
            auto last_it = upper_bound(arr.begin(),arr.end(),val);
            if(last_it - first_it > gap)
                return val;
        }
        return 0;
    }