Topic describes

Find a number that occurs more than half the length of the array. You can assume that the array is non-empty and that a given array always has most elements.

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

1. Map method

Create a map of values and the number of values, and then traverse the map to find most of the elements

Example code 1: Omitted

2. What is the best way to solve the problem

Since most elements are more than half the length of the array, the element in the middle of the array must be that element after sorting

Example code 2:

def majorityElement(self, nums: [int]) - >int:
    nums.sort()
    return nums[int(len(nums) / 2)]
Copy the code

3. Moore’s voting method

  1. Identify the first element of the array as the element to vote on, and iterate through the array starting with index=1
  2. If the iterated element is the same as the voting element, count+1, if different count-2
  3. If count=0, replace the voting element with the one currently traversed, and reset count=1

Since most elements have more than half the number of elements in the array, his count will be large during the voting process, and there won’t be enough different elements to reduce his count to zero

Example code 3:

def majorityElement(self, nums: [int]) - >int:
    moer = nums[0]
    count = 1
    for i in range(1.len(nums)):
        if nums[i] == moer:
            count += 1
        else:
            count -= 1
        if count == 0:
            count += 1
            moer = nums[i]
    return moer
Copy the code