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

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.

Solutions

Solution 1: Binary Search

We notice that the elements in the array \(nums\) are non-decreasing, that is, the elements in the array \(nums\) are monotonically increasing. Therefore, we can use the method of binary search to find the index \(left\) of the first element in the array \(nums\) that is greater than or equal to \(target\), and the index \(right\) of the first element in the array \(nums\) that is greater than \(target\). If \(right - left > \frac{n}{2}\), it means that the number of occurrences of the element \(target\) in the array \(nums\) exceeds half of the length of the array, so return \(true\), otherwise return \(false\).

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of the array \(nums\).

Python3JavaC++GoTypeScript

class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        left = bisect_left(nums, target)
        right = bisect_right(nums, target)
        return right - left > len(nums) // 2

class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        int left = search(nums, target);
        int right = search(nums, target + 1);
        return right - left > nums.length / 2;
    }

    private int search(int[] nums, int x) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

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

func isMajorityElement(nums []int, target int) bool {
    left := sort.SearchInts(nums, target)
    right := sort.SearchInts(nums, target+1)
    return right-left > len(nums)/2
}

function isMajorityElement(nums: number[], target: number): boolean {
    const search = (x: number) => {
        let left = 0;
        let right = nums.length;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (nums[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
    const left = search(target);
    const right = search(target + 1);
    return right - left > nums.length >> 1;
}

Solution 2: Binary Search (Optimized)

In Solution 1, we used binary search twice to find the index \(left\) of the first element in the array \(nums\) that is greater than or equal to \(target\), and the index \(right\) of the first element in the array \(nums\) that is greater than \(target\). However, we can use binary search once to find the index \(left\) of the first element in the array \(nums\) that is greater than or equal to \(target\), and then judge whether \(nums[left + \frac{n}{2}]\) is equal to \(target\). If they are equal, it means that the number of occurrences of the element \(target\) in the array \(nums\) exceeds half of the length of the array, so return \(true\), otherwise return \(false\).

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of the array \(nums\).

Python3JavaC++GoTypeScript

class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        left = bisect_left(nums, target)
        right = left + len(nums) // 2
        return right < len(nums) and nums[right] == target

class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        int n = nums.length;
        int left = search(nums, target);
        int right = left + n / 2;
        return right < n && nums[right] == target;
    }

    private int search(int[] nums, int x) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

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

func isMajorityElement(nums []int, target int) bool {
    n := len(nums)
    left := sort.SearchInts(nums, target)
    right := left + n/2
    return right < n && nums[right] == target
}

function isMajorityElement(nums: number[], target: number): boolean {
    const search = (x: number) => {
        let left = 0;
        let right = n;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (nums[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
    const n = nums.length;
    const left = search(target);
    const right = left + (n >> 1);
    return right < n && nums[right] === target;
}

Comments