LeetCode 1287. 有序数组中出现次数超过25%的元素

示例：
输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6
 
提示：
1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int i, n, prev = arr[0], count = 1;
        n = arr.size()/4+1;
        for(i = 1; i < arr.size(); ++i)
        {
        	if(arr[i] == prev)
            {
                count++;
                if(count >= n)
        		    return prev;
            }
        	else
        	{
        		count = 1;
        		prev = arr[i];
        	}
        }
        return prev;
    }
};

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int i, n = arr.size()/4;
        for(i = n; i < arr.size()-n; i++)
        {
        	if(arr[i-n] == arr[i] || arr[i] == arr[i+n])
        		return arr[i];
        }
        return -1;
    }
};

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int i, n = arr.size()/4+1;
        for(i = 0; i < arr.size(); i+=n)
        {
        	auto l = lower_bound(arr.begin(),arr.end(),arr[i]);
            auto r = upper_bound(arr.begin(),arr.end(),arr[i]);
            if(r-l >= n)
        		return arr[i];
        }
        return -1;
    }
};