Leetcode algorithm questions

Posted on Edited on In , Views:

Moore Voting Algorithm

[Leetcode 169] Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

1
2
Input: nums = [3,2,3]
Output: 3

Example 2:

1
2
Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

Follow-up: Could you solve the problem in linear time and in O(1) space?

Solution:

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
class Solution:
    # Moore Voting Algorithm
    def majorityElement(self, nums: List[int]) -> int:
        candidate = 0
        count = 0
        for num in nums:
            if count == 0:
                candidate = num

            if num == candidate:
                count += 1

            else:
                count -= 1

        return candidate

    def majorityElement_sort(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2] 

    def majorityElement_hashmap(self, nums: List[int]) -> int:
        m = defaultdict(int)
        for num in nums:
            m[num] += 1

        for k in m:
            if m[k] > len(nums) // 2:
                return k

        return 0