# 1150. Check If a Number Is Majority Element in a Sorted Array 检查一个数是否在数组中占绝大多数

@TOC

## # 题目描述

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.
``````

Note:

1. `1 <= nums.length <= 1000`
2. `1 <= nums[i] <= 10^9`
3. `1 <= target <= 10^9`

## # 解题方法

### # 字典

C++代码如下：

``````class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
return count[target] > nums.size() / 2;
}
};
``````

### # 二分查找

1. lower_bound(val):返回容器中第一个值【大于或等于】val的元素的iterator位置。
2. upper_bound(val): 返回容器中第一个值【大于】

C++代码如下：

``````class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int right = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
if (left >= nums.size() || nums[left] != target) return false;
return right - left > nums.size() / 2;
}
};
``````

## # 日期

2019 年 9 月 18 日 —— 今日又是九一八