leetcode/169_Majority_Element.py at master · annabechang/leetcode · GitHub

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
"""
169. Majority Element

Easy

1638

142

Favorite

Share
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2
"""
#Boyer–Moore majority vote
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        index, count = 0, 1

        for i in range(1,len(nums)):
            if nums[index] == nums[i]:
                count += 1
            else:
                count -= 1
                if count == 0:
                    index = i
                    count = 1
        return nums[index]

"""
Success
Details
Runtime: 48 ms, faster than 85.97% of Python3 online submissions for Majority Element.
Memory Usage: 14.2 MB, less than 84.55% of Python3 online submissions for Majority Element.
"""

#divide and conquer
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return None
        if len(nums) == 1:
            return nums[0]

        mid = len(nums) // 2
        l = self.majorityElement(nums[:mid])
        r = self.majorityElement(nums[mid:])

        if l == r:
            return l

        return [r,l][nums.count(l) > mid]

"""
Success
Details
Runtime: 140 ms, faster than 5.22% of Python3 online submissions for Majority Element.
Memory Usage: 14.3 MB, less than 53.71% of Python3 online submissions for Majority Element.


"""