Formatted question description: https://leetcode.ca/all/1150.html

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

Level

Easy

Description

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

Solution

Use binary search to find the leftmost index and the rightmost index of target, and calculate how many times target appears. If target appears more than half of the array’s length, then return true. Otherwise, return false.

  • class Solution {
        public boolean isMajorityElement(int[] nums, int target) {
            int length = nums.length;
            int leftIndex = findLeft(nums, target);
            int rightIndex = findRight(nums, target);
            if (leftIndex < 0 && rightIndex < 0)
                return false;
            else {
                int majorityCount = rightIndex - leftIndex + 1;
                return majorityCount > length / 2;
            }
        }
    
        public int findLeft(int[] nums, int target) {
            int low = 0, high = nums.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                int num = nums[mid];
                if (num == target) {
                    if (mid - 1 >= low && nums[mid - 1] == target)
                        high = mid - 1;
                    else
                        return mid;
                } else if (num < target)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            return -low - 1;
        }
    
        public int findRight(int[] nums, int target) {
            int low = 0, high = nums.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                int num = nums[mid];
                if (num == target) {
                    if (mid + 1 <= high && nums[mid + 1] == target)
                        low = mid + 1;
                    else
                        return mid;
                } else if (num < target)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            return -low - 1;
        }
    }
    
  • // OJ: https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/
    // Time: O(logN)
    // Space: O(1)
    class Solution {
    public:
        bool isMajorityElement(vector<int>& A, int target) {
            return upper_bound(begin(A), end(A), target) - lower_bound(begin(A), end(A), target) > A.size() / 2;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions