[LeetCode] 1150. Check If a Number Is Majority Element in a Sorted Array

Given an array nums sorted in non-decreasing order, and a number target, return True if and only if target is a majority element.

A majority element is an element that appears more than N/2 times in an array of length N.

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] <= 10^9
1 <= target <= 10^9

检查一个数是否在数组中占绝大多数。题意是给一个升序的数组和一个target数字，请你判断这个数字是否占整个数组的一半以上。

思路是二分法。既然是有序的数组，其实用for loop扫描一遍并且统计target number的出现次数也是可以的，但是这个做法在非常极端的test case会超时，所以这里优化的方法是二分法。用二分法去找target和target + 1这两个数字第一次出现的位置。两者的下标差距如果大于数组长度的一半则满足题意。

时间O(logn)

空间O(1)

Java实现

 1 class Solution {
 2     public boolean isMajorityElement(int[] nums, int target) {
 3         int len = nums.length;
 4         int first = helper(nums, target);
 5         int last = helper(nums, target + 1);
 6         return last - first > len / 2;
 7     }
 8 
 9     private int helper(int[] nums, int target) {
10         int left = 0;
11         int right = nums.length;
12         while (left < right) {
13             int mid = left + (right - left) / 2;
14             if (nums[mid] < target) {
15                 left = mid + 1;
16             } else {
17                 right = mid;
18             }
19         }
20         return left;
21     }
22 }

JavaScript实现

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} target
 4  * @return {boolean}
 5  */
 6 var isMajorityElement = function (nums, target) {
 7     let len = nums.length;
 8     let first = helper(nums, target);
 9     let last = helper(nums, target + 1);
10     return last - first > Math.floor(len / 2);
11 };
12 
13 var helper = function (nums, target) {
14     let left = 0;
15     let right = nums.length;
16     while (left < right) {
17         let mid = Math.floor(left + (right - left) / 2);
18         if (nums[mid] < target) {
19             left = mid + 1;
20         } else {
21             right = mid;
22         }
23     }
24     return left;
25 };

LeetCode 题目总结