169_Majority Element

[easy] [array]

Given an array of size n, find the majority element. The majority element is the element that appears more than⌊ n/2 ⌋times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

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

Solution 1:

Idea:

• Loop from left to right, record the frequency in a dictionary. Return the element when it appears enough times.

Time Complexity: $O(n)$

Space Complexity: $O(n)$

def majorityElement(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    myDict = {}
    for i in nums:
        if i in myDict:
            myDict[i] += 1
        else:
            myDict[i] = 1
        if myDict[i] > len(nums)//2:
            return i

Solution 2:

Idea:

• Sort the array, return the middle element.

Time Complexity: $O(n\log{n})$

Space Complexity: $O(1)$

def majorityElement(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    return sorted(nums)[len(nums)//2]