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

一、 题目

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2

限制：

1 <= 数组长度 <= 50000

注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、 题解

2.1 哈希表统计法

func majorityElementHash(_ nums: [Int]) -> Int {
    var temp: [Int : Int] = [:]
    
    for item in nums {
        if let count = temp[item] {
            if count == (nums.count / 2) {
                return item
            }
            temp[item] = count + 1
        }
        else {
            temp[item] = 1
        }
    }
    
    return nums[0]
}

1

2.2 数组排序法

将数组 nums 排序，数组中点的元素 一定为众数。

func majorityElementArray(_ nums: [Int]) -> Int {
    nums.sorted()[nums.count / 2]
}

2

2.3 摩尔投票法

核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N) O(1) 为本题的最佳解法。

func majorityElementMo(_ nums: [Int]) -> Int {
    var score = 0
    var x = 0
    for n in nums {
        if score == 0 {
            x = n
        }
        score += (x == n ? 1 : -1)
    }
    return x
}

3

算法学习笔记(78): 摩尔投票