【Leetcode热题100】1287.有序数组中出现次数超过25%的元素

问题背景

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

数据约束 1 ≤ a r r . l e n g t h ≤ 1 0 4 1 \le arr.length \le 10 ^ 4 1≤arr.length≤104 0 ≤ a r r [ i ] ≤ 1 0 5 0 \le arr[i] \le 10 ^ 5 0≤arr[i]≤105 解题过程

自己做的时候是用哈希表统计次数的，因为没有额外要求，还算符合题意。 看了 灵神的分析 发现能用二分查找实现，确实很巧妙。

具体实现 class Solution { public int findSpecialInteger(int[] arr) { int n = arr.length / 4; for (int i : new int[]{n, 2 * n + 1}) { int cur = arr[i]; if (binarySearch(arr, cur + 1) - binarySearch(arr, cur) > n) { return cur; } } return arr[3 * n + 2]; } private int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length; while (left < right) { int mid = left + ((right - left) >>> 1); if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } }