Clear O(n) solution in python, no data structure or sort.


  • 6
    K
    class Solution:
        # @param {integer[]} nums
        # @return {integer[]}
        def majorityElement(self, nums):
            a, b, ca, cb = 0, 1, 0, 0
            for num in nums:
                if a == num:
                    ca += 1
                elif b == num:
                    cb += 1
                elif ca == 0:
                    a, ca = num, 1
                elif cb == 0:
                    b, cb = num, 1
                else:
                    ca -= 1
                    cb -= 1
            ca = len([0 for num in nums if num == a])
            cb = len([0 for num in nums if num == b])
            res = []
            if ca > len(nums) / 3:
                res.append(a)
            if cb > len(nums) / 3:
                res.append(b)
            return res

  • 3
    J

    Can you really say it takes O(1) space if you have len([0 for num in nums if num == a])? That list comprehension could take up as much space as nums if all the numbers are a.


  • 0
    T

    O(1) space if you replace
    len([0 for num in nums if num == a])
    by
    sum(1 for num in nums if num == a) # generators ftw


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.