Python solution(sorting, hashmap, moore voting, bit manipulation)


  • 6
    X

    Refer to https://leetcode.com/discuss/67340/java-solutions-sorting-hashmap-moore-voting-manipulation
    Bit manipulation is somewhat different because of the python's syntax

    class Solution(object):
        def majorityElement(self, nums):
            nums.sort()
            return nums[len(nums)/2]
    
        # Boyer–Moore majority vote algorithm. Refer to:
        # https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm
        def majorityElement_moore(self, nums):
            majority_num = 0
            count = 0
            for num in nums:
                if count == 0:
                    majority_num = num
                if majority_num != num:
                    count -= 1
                else:
                    count += 1
            return majority_num
    
        # Hash table
        def majorityElement_hash(self, nums):
            num_len = len(nums)
            num_hash = {}
            for num in nums:
                num_hash[num] = num_hash.get(num, 0) + 1
                if num_hash[num] > num_len/2:
                    return num
    
        # Bit manipulation
        # Pay attention: in python -2147483648 >> 31 = -1
        def majorityElement_bit(self, nums):
            bit_bucket = [0 for i in range(33)]
            for num in nums:
                bit_bucket[32] += (num >> 32) & 1
                for i in range(32):
                    bit_bucket[i] += (abs(num) >> i) & 1
    
            majority_num = 0
            nums_len = len(nums)
            for i in range(32):
                if bit_bucket[i] > nums_len / 2:
                    majority_num += 1 << i
            if bit_bucket[32] > nums_len / 2:
                majority_num *= -1
            return majority_num

  • 0
    S

    nice summary!


Log in to reply
 

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