Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

Problem description

Given an array of length n, find a number that occurs more than half the length. For example, enter an array of length 9 [1,2,3,2,2,2,5,4,2]. Since the number 2 appears in the array five times, more than half the length of the array, 2 is printed.

Example:

Input:,2,3,2,2,2,5,4,2 [1]

Output: 2

To analyze problems

Hash table method

The easiest way to think about it is to use a hash table, to count the number of occurrences of each number, it is easy to find the superior number.

Def majorityElement(nums): def majorityElement(nums) = {} for x in nums: if x in data_count: data_count[x] = data_count[x] + 1 else: Data_count [x] = 1 max_value=0 max_key=0 value=data_count[key] if value>max_value: Max_value =value max_key=key return max_key data=[1,2,3,2,2, 5,4,2] print(majorityElement(data)Copy the code

The time complexity of this algorithm is O(n), and the space complexity is also O(n).

Sorting algorithm

If we sort the array, the midpoint of the sorted array must be the mode.

def majorityElement(nums): Nums [len(nums) // 2] data=[1,2,3,2,2, 5,4,2] print(majorityElement(data))Copy the code

Boyer-moore voting algorithm

The classic solution to this problem is the Boyer-Moore voting algorithm. The core idea of Boyer-Moore voting algorithm is that the number of votes is positive and negative offset, that is, in the case of mode, we add the number of votes +1, and in the case of non-mode, we add the number of votes -1, so the sum of all votes must be greater than 0.

We assume that the mode of the array nums is X and the length of the array is n. We can easily know that if the sum of the first a numbers in the array is 0, then the sum of the remaining n-a numbers must be greater than 0, that is, the mode of the last n-a numbers is still X.

The first element of the array is n1, the mode of the array is x, and we iterate and count the votes. When the sum of votes is 0, the mode of the remaining elements of the array must also be X, because:

  1. When n1 is equal to x, of all the numbers that cancel out, half of them are mode x.
  2. When n1 is not equal to x, the mode is at least 0 and at most half of all the numbers that cancel out.

So, in removing m characters, we remove at most half of the mode, so x is still mode in the remaining n-m elements. Using this feature, we can shrink the remaining array range every time we encounter a sum of votes of 0. When the traversal is complete, the number assumed in the last round is the mode.

Class Solution: def majorityElement(self, nums): # count =0 If num==x: counts=counts+1 else: counts=counts-1 return xCopy the code

The time complexity of the algorithm is O(n) and the space complexity is O(1).