“This is the 13th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

1. Title 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.

Data range: n≤50000, array element value 0≤val≤10000

Requirements: Space complexity: O(1), time complexity: O(n)

Second, the problem solving

If you want to find an element in an array that is more than half the length of the array, you can’t tell that this element is the most and only certain element in the array.

There are many ways to find this number.

(1) the Hash method

The simplest and most common way to do this is to iterate through the array, create and use a map to store the number of occurrences of each number, and return that number when it is greater than half the length of the array.

func MoreThanHalfNum_Solution( numbers []int ) int {
    // write code here
    mp := make(map[int]int)
    for _, num := range numbers {
        mp[num]++
        if mp[num] >= (len(numbers) + 1) / 2 {
            return num
        }
    }
    return - 1
}
Copy the code

The worst time complexity of this method is O(n), which is ideal. But it takes O(n) extra space, which is not true.

(2) sorting method

Since the number of occurrences is greater than half, the median and mode of the array are the same. That is, if processed in ascending or descending order, the element in the middle of the array must be the target element.

import "sort"
func MoreThanHalfNum_Solution( numbers []int ) int {
    // write code here
    sort.Ints(numbers)
    return numbers[len(numbers) / 2]}Copy the code

After sorting, the time complexity of locating the intermediate elements is negligible, so just calculate the sorting algorithm.

Depending on the sorting algorithm, time and space complexity are not quite the same. However, no matter which sorting algorithm is used, the time complexity is O(n) and the space complexity is O(1).

(3) ring method

Because the number we’re looking for is so numerically dominant, even if all the other numbers add up to less than that number.

So let’s build a “ring” for numbers and follow these rules:

  1. Each number has a chance to enter the ring, and the same number is a faction;
  2. [Fixed] There can be only one faction number or no number in the ring.
  3. If the arena is empty or the same number of factions exists, you can increase the number of factions by one. If the number in the ring is different from the joining number, it is “lose-lose” and the number in the ring is reduced by one.

In the worst-case scenario, the number with the largest number is at war with all the other numbers at the same time, following a one-to-one interaction ratio, and the remaining number must also be the number we are looking for.

In terms of implementation, we only need to use two variables to store the opponent camp and the number respectively, and then iterate through the simulation process above.

func MoreThanHalfNum_Solution( numbers []int ) int {
    // write code here
    // The initial arena is empty
    host := - 1
    hostNum := 0
    for _, num := range numbers {
        if hostNum == 0 {
            // Grab an empty arena
            host = num
            hostNum = 1
        } else {
            // The ring is occupied
            if host == num {
                // It's my team
                hostNum++
            } else {
                hostNum--
            }
        }
    }
    return host
}
Copy the code

In this method, a complete traversal must be completed, and the time complexity is stable as O(n). Only two variables need to be maintained, and the space complexity is O(1), which meets the requirements of the topic.