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

 

Constraints:

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

Solution(javascript)

/*
 * @lc app=leetcode id=1287 lang=javascript
 *
 * [1287] Element Appearing More Than 25% In Sorted Array
 */

// @lc code=start
// /** 检测分隔点是不行
//  * O(n)
//  * @param {number[]} arr
//  * @return {number}
//  */
// const findSpecialInteger = function (arr) {
//   const len = arr.length / 4
//   let prevNum = null
//   let count = 0
//   for (const num of arr) {
//     if (num === prevNum) {
//       count += 1
//     } else {
//       prevNum = num
//       count = 1
//     }
//     if (count > len) {
//       return num
//     }
//   }
// }
/** Binary Search O(log(n))
 * @param {number[]} arr
 * @return {number}
 */
const findSpecialInteger = function (arr) {
  const len = arr.length / 4
  const search = (left, right, target, direction = 'left') => {
    let index = -1
    while (left <= right) {
      const middle = Math.floor(left + (right - left) / 2)
      if (arr[middle] === target) {
        index = middle
        if (direction === 'left') {
          right = middle - 1
        } else {
          left = middle + 1
        }
      } else if (arr[middle] < target) {
        left = middle + 1
      } else {
        right = middle - 1
      }
    }
    return index
  }
  for (let i = 1; i <= 3; i++) {
    const index = Math.floor(len * i)
    const num = arr[index]
    const loIndex = search(0, index, num, 'left')
    const hiIndex = search(index, arr.length - 1, num, 'right')
    if (hiIndex - loIndex + 1 > len) {
      return num
    }
  }
}
// @lc code=end