Leetcode: Majority Element II

Identity number which appears exactly once.



Given an integer array of size n, find all elements that appear more than n/3 times. The algorithm should run in linear time and in O(1) space.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/majority-element-ii
## Basic Ideas:
##       No more than 2 elements would be qualified.
## Complexity: Time O(n), Space O(1)
## Sample Data:
##    1 2 3 2 3 3
## Asummption:
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length = len(nums)
        if length == 0:
            return []
        n1, n2 = None, None
        c1, c2 = 0, 0
        for num in nums:
            if num == n1:
                c1 += 1
            elif num == n2:
                c2 += 1
            elif c1 == 0:
                n1, c1 = num, 1
            elif c2 == 0:
                n2, c2 = num, 1
            else:
                c1, c2 = c1 - 1, c2 - 1
        c1, c2 = 0, 0
        for num in nums:
            if num == n1:
                c1 += 1
            elif num == n2:
                c2 += 1
        # print("n1: %d, c1: %d, n2: %d, c2: %d. length: %d" % (n1, c1, n2, c2, length))
        res = []
        if c1 > length/3:
            res.append(n1)
        if c2 > length/3:
            res.append(n2)
        return res

# s = Solution()
# print s.majorityElement([1, 2])
# print s.majorityElement([1,2,1,1,1,3,3,4,3,3,3,4,4,4])
# print s.majorityElement([1,1,1,2,3,4,5,6])
# print s.majorityElement([1, 2, 3, 2, 3, 3])
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.