source: https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/description/
Check If a Number Is Majority Element in a Sorted Array
Table of Contents
Description
Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is a majority element, or false otherwise.
A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.
Example 1:
Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.
Example 2:
Input: nums = [10,100,101,101], target = 101
Output: false
Explanation: The value 101 appears 2 times and the length of the array is 4.
Thus, 101 is not a majority element because 2 > 4/2 is false.
Constraints:
- 1 <= nums.length <= 1000
- 1 <= nums[i], target <= 109
- nums is sorted in non-decreasing order.
Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public boolean isMajorityElement(int[] nums, int target) { int left = 0; int right = nums.length-1; while(left < right){ int mid = left + (right-left)/2; if(nums[mid] >= target){ right = mid; } else { left = mid+1; } } if(nums[left]==target){ int count = 1; int p = left+1; while(p<nums.length && nums[p]==target){ count++; p++; } return count > (int)Math.floor(nums.length / 2); } return false; } } |