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

Problem #

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

Problem Summary #

Given a non-decreasing sorted integer array, it is known that exactly one integer in this array appears more than 25% of the total number of elements. Find and return this integer.

Note:

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

Solution Approach #

• Given a non-decreasing sorted array, output the element whose occurrence count exceeds 25% of the total number of elements.
• This is an easy problem. Since the array is already sorted in non-decreasing order, we only need to check whether arr[i] == arr[i+n/4].

Code #

func findSpecialInteger(arr []int) int {
	n := len(arr)
	for i := 0; i < n-n/4; i++ {
		if arr[i] == arr[i+n/4] {
			return arr[i]
		}
	}
	return -1
}