描述

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

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

• 数据范围：n≤50000，数组中元素的值 0≤val≤10000
• 要求：空间复杂度：O(1)，时间复杂度 O(n)
• 保证数组输入非空，且保证有解

示例

// 输入：
[1,2,3,2,2,2,5,4,2]
// 返回值：
2

// 输入：
[3,3,3,3,2,2,2]
// 返回值：
3

// 输入：
[1]
// 返回值：
1

解题思路

哈希法

• 先遍历一遍数组，将每个元素出现的次数存在入 map 中，再遍历 map，找出次数大于数组一半的数

候选法（优化）

• 如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。

代码实现

哈希法：

/**
 * [JZ39-简单] 数组中出现次数超过一半的数字（哈希法）
 *
 * @param numbers int整型一维数组
 * @return int整型
 */
func moreThanHalfNum(numbers []int) int {
    length := len(numbers)
    if 1 == length {
        return numbers[0]
    }

    hash := map[int]int{}
    for _, v := range numbers {
        if _, ok := hash[v]; ok {
            hash[v] += 1
        } else {
            hash[v] = 1
        }
    }

    for k, v := range hash {
        if v > length/2 {
            return k
        }
    }

    return 0
}

候选法：

/**
 * [JZ39-简单] 数组中出现次数超过一半的数字（候选法）
 *
 * @param numbers int整型一维数组
 * @return int整型
 */
func moreThanHalfNum(numbers []int) int {
    length := len(numbers)
    if 1 == length {
        return numbers[0]
    }

    cond, count := -1, 0
    for _, v := range numbers {
        if 0 == count {
            cond = v
            count++
        } else {
            if cond == v {
                count++
            } else {
                count--
            }
        }
    }

    count = 0
    for _, v := range numbers {
        if v == cond {
            count++
        }
    }

    if count > length/2 {
        return cond
    } else {
        return 0
    }
}