169.多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

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

示例 1：

1
2
输入：[3,2,3]
输出：3

在数组中占比已经超过一半的数字

Solution：排序查找

1
2
3
4
5
6
7
class Solution {
    public int majorityElement(int[] nums) {
         
         Arrays.sort(nums);
         return nums[nums.length/2];
    }
}

因为元素在数组中的出现次数大于了n/2，所以下标为n/2的元素一定是多数元素

Solution1：Boyer-Moore 投票算法

Boyer-Moore 算法,我们首先给出 Boyer-Moore 算法的详细步骤：

  • 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；

  • 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：

    • 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
    • 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。

  • 在遍历完成后，candidate 即为整个数组的众数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    // majorityElement方法接收一个整数数组nums作为参数
    public int majorityElement(int[] nums) {
        // count用于记录当前候选元素的出现次数
        int count = 0;
        // candidate用于存储当前的候选多数元素，初始化为null
        Integer candidate = null;

        // 遍历数组中的每个元素
        for (int num : nums) {
            // 如果当前计数为0，选择新的候选元素
            if (count == 0) {
                candidate = num;
            }
            // 如果当前元素等于候选元素，计数加1，否则减1
            // 这里的核心思想是，如果一个元素是多数元素，那么它出现的次数比其他所有元素出现次数的和还要多
            count += (num == candidate) ? 1 : -1;
        }

        // 返回最后确定的候选元素
        return candidate;
    }
}

投票算法证明：

  1. 如果候选人不是major则major会和其他非候选人一起反对候选人,所以候选人一定会下台(coumt==0时发生换届选举)
  2. 如果候选人是major , 则major 会支持自己，其他候选人会反对，同样因为major 票数超过一半，所以major 一定会成功当选