Question source, 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.

0. Problem-solving ideas

Three ways to solve the problem.

1. Brute Force

We can exhaust the search space in quadratic time by checking whether each element is the majority element.

In the first loop, we traverse each x. In the second loop, we calculate the number of each x and compare them with n/2 one by one. If greater than, return the number.

Complexity

  • Time complexity: O(n^2)
    • The brute force algorithm contains two nested for loops that each run for n iterations, adding up to quadratic time complexity.
  • Space complexity: O(1)
    • The brute force solution does not allocate additional space proportional to the input size.

2. HashMap

We use one nested for loop here. Take x as key, the count of x in the nums as the value.

Complexity

  • Time complexity: O(n)
    • We iterate over nums once and make a constant time HashMap insertion on each iteration.
  • Space complexity: O(n)
    • the HashMap can contain n - [ n/2 ] associations, so it occupies O(n) space.

3. Sorting

We sort nums. Note the majority element is the element that appears more than ⌊ n/2 ⌋ times. so we return the n/2-th elements in nums.

Complexity

  • Time complexity: O(n)
    • Sorting the array costs O(nlogn) time in Python and Java, so it dominates the overall runtime.
  • Space complexity: O(1) or O(n)
    • We may do nothing on num or fully sort nums.

Code

Code file

1
2
3
4
5
class Solution:
    # method 2 
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

4. Divide and Conquer

Divide and conquer method Divide and conquer method is to reduce the whole problem into small problems to solve one by one, and divide the array into simple parts.

  • This question divides the array into two halves, recursively finds the mode in the left array, and recursively finds the mode in the right array.
  • Compare the two arrays with the same return value (left and right) via help
  • If the recursive return values ​​of both sides are the same, Return to any interval directly (left and right)
  • If the two recursive return values ​​are different, traverse the combined left and right intervals to find the one with the most occurrences as the return value of this interval
  • This method is repeated on the left and right sides of the array until it can Easily get the recursive boundary conditions of the elements of the array of length 1: There is only one element in the interval, no need to divide, and return this element directly (the question says You may assume that the array is non-empty and the majority element always exist in the array.)

分治法分治法是将整个问题化简为一个一个的小问题去解，将数组分成简单的几部分.

  • 此题将数组分为两半，递归地在左边数组找众数，递归地在右边数组找众数

  • 比较两边数组通过help返回值（left and right）是否相同

  • 若两边递归返回值相同，直接返回任意区间（left and right）

  • 若两边递归返回值不同，遍历左右合并后的区间，找到出现次数最多的那个，作为这个区间的返回值

  • 该方法在数组的左右两边重复进行，直到可以轻松获得长度为1的数组的元素为止

递归边界条件：区间只有一个元素，不用再分，直接返回这个元素 （题中说了You may assume that the array is non-empty and the majority element always exist in the array.）

Complexity

  • Time complexity: O(nlogn)

    • Each recursive call to majority_element_rec performs two recursive calls on subslices of size n/2 and two linear scans of length n. Therefore, the time complexity of the divide & conquer approach can be represented by the following recurrence relation:T(n)=2T(n/2)+2n

    • By the master theorem, the recurrence satisfies case 2, so the complexity can be analyzed as such: T(n) = O(nlogn)

  • Space complexity: O(logn)
    • Because the algorithm "cuts" the array in half at each level of recursion, it follows that there can only be O(lgn) "cuts" before the base case of 1 is reached. It follows from this fact that the resulting recursion tree is balanced, and therefore all paths from the root to a leaf are of length O(lgn).

Code

Code file

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return self.help(0,len(nums)-1,nums)
        
        
    def help(self,low,high,nums):
        # base case; the only element in an array of size 1 is the majority
        # element.
        if low == high:
            return nums[low]
        
        # recurse on left and right halves of this slice.
        mid = (high-low)//2 + low
        left = self.help(low,mid,nums)
        right = self.help(mid+1,high,nums)

        # if the two halves agree on the majority element, return it.
        if left == right:
            left

        # otherwise, count each element and return the "winner".
        left_count = sum(1 for i in range(low,high+1) if nums[i]==left)
        right_count = sum(1 for i in range(low,high+1) if nums[i]==right)
        return left if left_count > right_count else right

Summary

Sorting Divide and Conquer
Runtime 156 ms, faster than 86.68% of Python3 online submissions 304 ms, faster than 5.25% of Python3 online submissions
Memory Usage 15.5 MB, less than 18.62% of Python3 online submissions 15.6 MB, less than 18.62% of Python3 online submissions