Leetcode 169: Majority Element

 

Code

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        major = ''
        for n in nums:
            if count == 0:
                major = n
            if n == major:
                count += 1
            else:
                count -= 1
        return major

 

Idea

This is the algorithm called Moore voting. More details can be found: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/. My understanding is that major is the current number whose occurrences has not been outnumbered by other numbers. The majority element will eventually has its occurrence count being positive. 

 

Code

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        
        for i in xrange(32):
            ones, zeros = 0, 0
            for n in nums:
                # right shift for negative number is weird 
                # in Python. So apply on absolute value.
                if (abs(n) >> i) & 1:
                    ones += 1
                else:
                    zeros += 1
            if ones > zeros:
                ans = ans | (1 << i)
                
        # in python, you need to count signs separately.        
        positive, negative = 0, 0
        for n in nums:
            if n > 0:
                positive += 1
            else:
                negative += 1
        if positive > negative:
            return ans
        else:
            return -ans

 

Idea

Borrow the idea from Single Number II. Count one’s and zeros appearing in each bit. The majority element dominates those counts so you can reconstruct the number.

Reference: https://discuss.leetcode.com/topic/6286/share-my-solution-java-count-bits

 

 

Code (divide and conquer)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return None
        if len(nums) == 1:
            return nums[0]
        a = self.majorityElement(nums[:len(nums)/2])
        b = self.majorityElement(nums[len(nums)/2:])
        if a == b:
            return a
        else:
            return a if nums.count(a) > len(nums)/2 else b

 

Idea

THink from top to bottom. When nums have two partitions, and we already know a is the majority element of the first partition (line 11) and b is the majority element of the second partition (line 12). If c is the majority element, then either:

1. a == b == c, i.e., c is the majority element in both partitions
2. a != b. then c must be equal to either a or b. 

We can prove 2 by contradiction. If c != a and c != b, then c is not the majority element in either partition. That means, occurrences(c in 1st partition) <= len(1st partition)/2 and occurrences(c in 2nd partition) <= len(2nd partition)/2. Therefore, occurences(c in nums) <= len(nums)/2, which contradicts with the fact that c is the majority element. So we recursively can prove the correctness of every level of divide-and-conquer.

 

Code (Sorting)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(nums)[len(nums)/2]

 

Idea

After sorting, the majority element must occupy the position len(nums)/2