Boyer-Moore Voting Algorithm

2018-10-23

Algorithms

topic

Catalogue

1. 169. Majority Element
1. 1.1. Solution1. Hash Table
2. 1.2. Solution2. Voting Algorithm
2. 229. Majority Element II
1. 2.1. Solution1. Hash table
2. 2.2. Solution2. Voting Algorithm
3. Majority Element III
4. Majority Element IV
5. 277. Find the Celebrity
1. 5.1. Solution1. Divede and Conquer O(nlogn)
2. 5.2. Solution2. Voting O(n)

169. Majority Element

Solution1. Hash Table

Time : O(n), Space : O(n)

class Solution(object):
    def majorityElement(self, nums):
        n = len(nums)
        dic = collections.defaultdict(int)
        for num in nums:
            dic[num] += 1
            if dic[num] > n/2:
                return num

Solution2. Voting Algorithm

Time : O(n), Space :O(1)

Maintain a pair candidate, counter
When a new element x comes in,

if counter == 0, just set candidate = x, counter = 1

else if x == candidate, counter ++ else counter –

class Solution(object):
    def majorityElement(self, nums):
        candidate = None
        counter = 0

        for num in nums:
            if counter == 0:
                candidate = num
                counter = 1
            else:
                counter += 1 if candidate == num else -1
        return candidate

229. Majority Element II

Solution1. Hash table

Time : O(n), Space : O(n)

class Solution(object):
    def majorityElement(self, nums):
        n = len(nums)
        dic = collections.defaultdict(int)
        res = set()
        for num in nums:
            dic[num] += 1
            if dic[num] > n / 3:
                res.add(num)
        return list(res)

Solution2. Voting Algorithm

Time : O(n), Space : O(1)

class Solution(object):
    def majorityElement(self, nums):
        if not nums:
            return []
        n = len(nums)
        can1, can2 = 0, 1
        cnt1, cnt2 = 0, 0
        for num in nums:
            if can1 == num:
                cnt1 += 1
            elif can2 == num:
                cnt2 += 1
            else:
                if cnt1 == 0:
                    cnt1, can1 = 1, num
                elif cnt2 == 0:
                    cnt2, can2 = 1, num
                else:
                    cnt1 -= 1
                    cnt2 -= 1

        return [can for can in [can1,can2] if nums.count(can) > n // 3]

Majority Element III

duplicates > [1/k], we need k-1 candidates, so the space complexity is O(k)

Majority Element IV

what if the input in sorted, you wanna find the majority number appears n / 4 times!

277. Find the Celebrity

Solution1. Divede and Conquer O(nlogn)

class Solution(object):
    def findCelebrity(self, n):
        if n <= 1: return n

        cand = self.find_cands(range(n))
        for i in range(n):
            if i == cand:
                continue

            if knows(cand, i):
                return -1

            if not knows(i, cand):
                return -1
        return cand

    def find_cands(self, nums):
        n = len(nums)
        # Base Case
        if n == 1:
            return nums[0]

        if n == 2:
            if knows(nums[0], nums[1]):
                return nums[1]
            else:
                return nums[0]

        p1 = self.find_cands(nums[:n//2+1])
        p2 = self.find_cands(nums[n//2+1:])

        return p2 if knows(p1, p2) else p1

Solution2. Voting O(n)

Something like the Voting algorithm

class Solution(object):
    def findCelebrity(self, n):
        if n <= 1:
            return n

        cand = 0
        for i in range(1, n):
            if knows(cand, i):
                cand = i

        if any(knows(cand, i) for i in range(cand)):
            return -1

        if any(not knows(i, cand) for i in range(n)):
            return -1

        return cand