Question

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

English Version

题目描述

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

 

示例：

输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6

 

提示：

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

解法

方法一

class Solution:
  def findSpecialInteger(self, arr: List[int]) -> int:
    n = len(arr)
    for i, val in enumerate(arr):
      if val == arr[i + (n >> 2)]:
        return val
    return 0

class Solution {
  public int findSpecialInteger(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; ++i) {
      if (arr[i] == arr[i + (n >> 2)]) {
        return arr[i];
      }
    }
    return 0;
  }
}

class Solution {
public:
  int findSpecialInteger(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; ++i)
      if (arr[i] == arr[i + (n >> 2)]) return arr[i];
    return 0;
  }
};

func findSpecialInteger(arr []int) int {
  n := len(arr)
  for i, val := range arr {
    if val == arr[i+(n>>2)] {
      return val
    }
  }
  return 0
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var findSpecialInteger = function (arr) {
  const n = arr.length;
  for (let i = 0; i < n; ++i) {
    if (arr[i] == arr[i + (n >> 2)]) {
      return arr[i];
    }
  }
  return 0;
};

class Solution {
  /**
   * @param Integer[] $arr
   * @return Integer
   */
  function findSpecialInteger($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
      if ($arr[$i] == $arr[$i + ($len >> 2)]) {
        return $arr[$i];
      }
    }
    return -1;
  }
}