A Python Solution Beats 97.8%


  • 0
    class Solution(object):
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            pool = []
            n = len(nums)
            for i in xrange(n):
                if nums[i] not in pool:
                    if nums.count(nums[i]) > n/2:
                        return nums[i]
                    pool.append(nums[i])

  • 0
    C

    I use a dict instead of your 'pool'. However, it's slower. Dont know how OJ works...


  • 0
    A

    maybe there is some bug?i submit the same code,and i found i just beat 35.8%


  • 0
    P

    is the pool only for efficiency thing? for example in 1112222 it gets the first 1 in pool and see its counts less than len/2, so later on when it scans the second and thrid 1, it will just pass. ago straight to nums[3] which is 2.?
    i guess if you don't use pool, it should still work>? just with more .count computation? i was trying this, and didn't get it work


  • 0

    @carlonelong Yes a dict should be more search efficient than a list. The overhead dominates the computation time so it could be quite random (run multiple times you could get quite different computational time). I have to admit that it is not ideal to compare the efficiency solely based on the one-time computation time. I will edit my post.


  • 0

    @acezio I think the computation time is mainly dominated by the overhead in such a small algorithm case.


  • 0

    @peng1774 Yes you are right! pool let you get pass those visited elements.


Log in to reply
 

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