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

原题链接在这里：https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/description/

题目：

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

Example 2:

Input: arr = [1,1]
Output: 1

Constraints:

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 105

题解：

To find the answer, for the interval length t = arr.length / 4, the beginning arr[i] == arr[i + t], then that is the answer.

Time Complexity: O(n). n = arr.length.

Space: O(1).

AC Java:

 1 class Solution {
 2     public int findSpecialInteger(int[] arr) {
 3         int n = arr.length;
 4         int t = n / 4;
 5         for(int i = 0; i < n - t; i++){
 6             if(arr[i] == arr[i + t]){
 7                 return arr[i];
 8             }
 9         }
10 
11         return -1;
12     }
13 }