摩尔投票

BM51 数组中出现次数超过一半的数字

描述

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：n \le 50000n≤50000，数组中元素的值 0 \le val \le 100000≤val≤10000

要求：空间复杂度：O(1)O(1)，时间复杂度 O(n)O(n)

输入描述：

保证数组输入非空，且保证有解

示例

输入：

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

返回值：2

算法过程分析

核心思想：出现不一样则可定不是，因为要过一半，就要一半一样的

第1轮

num = 1

count = 1

第2轮

发现是1了，所以1的票–，变成0，就换人了，变成2且票为1

num = 2

count = 1

第3轮

同理

num = 3

count = 1

第4轮

同理

num = 2

count = 1

第5轮

num = 2

count = 2

第6轮

num = 2

count = 3

第7轮

发现是5，不是2，减少一张票

num = 2

count = 2

第8轮

发现是4，不是2，减少一张票

num = 2

count = 1

第9轮

num = 2

count = 2

结束，输出num，也就是2

代码

摩尔投票

package main

/**
 *
 * @param numbers int整型一维数组
 * @return int整型
 */
func MoreThanHalfNum_Solution(numbers []int) int {
	// write code here

	num, count := numbers[0], 1

	for i := 1; i < len(numbers); i++ {
		if num == numbers[i] {
			count++
			continue
		} else {
			count--
			if count == 0 {
                //不要担心i+1越界，因为还没到众数
                i++
				num, count = numbers[i], 1
			}
		}
	}

	return num
}

哈希map

package main

/**
 * 
 * @param numbers int整型一维数组 
 * @return int整型
*/
func MoreThanHalfNum_Solution( numbers []int ) int {
    // write code here
    
    halfLen,res := len(numbers)/2,make(map[int]int)
    
    for _,v := range numbers{
        res[v]++
        if res[v] > halfLen{
            return v
        }
    }
    
    return 0
}

排序取中间

package main

import "sort"


/**
 *
 * @param numbers int整型一维数组
 * @return int整型
 */
func MoreThanHalfNum_Solution( numbers []int ) int {
    // write code here
    
    sort.Ints(numbers)
    return numbers[len(numbers)/2]
}

PREVIOUSUML系统分析小工具介绍

NEXTRationalRose的小坑