题解 | 数组中出现次数超过一半的数字

package main

import (
// "sort"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param numbers int整型一维数组
 * @return int整型
 */
func MoreThanHalfNum_Solution(numbers []int) int {
	// write code here
	// sort.Ints(numbers) // 升序

	// sort.Slice(numbers, func(i, j int) bool{
	//     return numbers[i] > numbers[j] // 降序
	// })

	// numbers = QiuckSort(numbers)
	// len := len(numbers)
	// return numbers[(len) / 2]

	// return Hash(numbers)

	// 投票法
	return Vote(numbers)
}

func Vote(numbers []int) int {
	count := 1
	res := numbers[0]

	for _, val := range numbers[1:] {
		if val == res {
			count++
		} else {
			count--
		}
		if count == 0 {
			count = 1
			res = val
		}
	}

	return res
}

func Hash(numbers []int) int {
	hash := make(map[int]int)
	for _, val := range numbers {
		hash[val]++
	}

	maxKey := 0
	maxVal := 0

	for key, val := range hash {
		if val >= maxVal {
			maxKey = key
			maxVal = val
		}
	}

	return maxKey
}

func QiuckSort(numbers []int) []int {
	if len(numbers) <= 1 {
		return numbers
	}

	pre := numbers[0]
	var left, right []int
	for _, val := range numbers {
		if val < pre {
			left = append(left, val)
		} else {
			right = append(right, val)
		}
	}

	return append(append(left, pre), right...)
}