Leetcode - Check If a Number Is Majority Element in a Sorted Array

violet posted @ Mar 24, 2020 01:34:21 AM in 算法 with tags Algorithm BinarySearch Golang array , 241 阅读

https://leetcode.com/problems/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.

func isMajorityElement(nums []int, target int) bool {
    left := 0
    right := len(nums) -1
    var mid int
    for left <= right {
        mid = (left+right)/2
        if target == nums[mid] {
            break
        }
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid -1
        }
    }
    if nums[mid] != target {
        return false
    }
    i := mid-1
    j := mid+1
    count := 1
    for i >= 0 && nums[i] == target {
        i--
        count++
    }
    for j < len(nums) && nums[j] == target {
        j++
        count++
    }
    
    return count > len(nums)/2
}