Boyer-Moore Voting Algorithm

Algorithms
topic
Catalogue
  1. 1. 169. Majority Element
    1. 1.1. Solution1. Hash Table
    2. 1.2. Solution2. Voting Algorithm
  2. 2. 229. Majority Element II
    1. 2.1. Solution1. Hash table
    2. 2.2. Solution2. Voting Algorithm
  3. 3. Majority Element III
  4. 4. Majority Element IV
  5. 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)
    1
    2
    3
    4
    5
    6
    7
    8
    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)
  1. Maintain a pair candidate, counter
  2. When a new element x comes in,
  • if counter == 0, just set candidate = x, counter = 1
  • else if x == candidate, counter ++ else counter –
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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)

1
2
3
4
5
6
7
8
9
10
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
Share