1287. Element Appearing More Than 25% In Sorted Array*

​​https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/​​

題目描述

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      

• ​

  ​1 <= arr.length <= 10^4​

  ​
• ​

  ​0 <= arr[i] <= 10^5​

  ​

C++ 實作 1

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

擴充閱讀