Check If a Number Is Majority Element in a Sorted Array
给一个sorted的数组和一个target, 求target在数组里是不是majority. 因为是sorted所以用二叉搜索做,先找左边界, 然后用+1找右边界.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public boolean isMajorityElement(int[] nums, int target) { int left = bs(nums, target); int right = bs(nums, target+1); return right - left > nums.length / 2; } private int bs(int[] nums, int target) { int left = 0; int right = nums.length; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } return left; } } |