Skip to content

17.10. Find Majority Element

Description

A majority element is an element that makes up more than half of the items in an array. Given a positive integers array, find the majority element. If there is no majority element, return -1. Do this in O(N) time and O(1) space.

Example 1: 


Input: [1,2,5,9,5,9,5,5,5]

Output: 5

 

Example 2: 


Input: [3,2]

Output: -1

 

Example 3: 


Input: [2,2,1,1,1,2,2]

Output: 2

Solutions

Solution 1

1
2
3
4
5
6
7
8
9
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = m = 0
        for v in nums:
            if cnt == 0:
                m, cnt = v, 1
            else:
                cnt += 1 if m == v else -1
        return m if nums.count(m) > len(nums) // 2 else -1