leetCode-0169_求众数

Posted on | In |

题目描述

英文题目

  • Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

    You may assume that the array is non-empty and the majority element always exist in the array.

    Example 1:

    1
    2
    Input: [3,2,3]
    Output: 3

    Example 2:

    1
    2
    Input: [2,2,1,1,1,2,2]
    Output: 2
中文题目

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

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

      示例 1:

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

      示例 2:

      1
      2
      输入: [2,2,1,1,1,2,2]
      输出: 2

解决方法

方法一
  • 描述

一种是用哈希表，这种方法需要O(n)的时间和空间，另一种是用一种叫摩尔投票法 Moore Voting，需要O(n)的时间和O(1)的空间，比前一种方法更好。这种投票法先将第一个数字假设为众数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。然后看此时计数器的值，若为零，则将下一个值设为候选众数。以此类推直到遍历完整个数组，当前候选众数即为该数组的众数。不仔细弄懂摩尔投票法的精髓的话，过一阵子还是会忘记的，首先要明确的是这个叼炸天的方法是有前提的，就是数组中一定要有众数的存在才能使用，下面我们来看本算法的思路，这是一种先假设候选者，然后再进行验证的算法。我们现将数组中的第一个数假设为众数，然后进行统计其出现的次数，如果遇到同样的数，则计数器自增1，否则计数器自减1，如果计数器减到了0，则更换下一个数字为候选者。这是一个很巧妙的设定，也是本算法的精髓所在，为啥遇到不同的要计数器减1呢，为啥减到0了又要更换候选者呢？首先是有那个强大的前提存在，一定会有一个出现超过半数的数字存在，那么如果计数器减到0了话，说明目前不是候选者数字的个数已经跟候选者的出现个数相同了，那么这个候选者已经很weak，不一定能出现超过半数，我们选择更换当前的候选者。那有可能你会有疑问，那万一后面又大量的出现了之前的候选者怎么办，不需要担心，如果之前的候选者在后面大量出现的话，其又会重新变为候选者，直到最终验证成为正确的众数，佩服算法的提出者啊

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int majorityElement(int* nums, int numsSize) {
    int major = 0;
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (count == 0) {
            major = nums[i];
            count += 1;
        }
        else if (major == nums[i]) {
            count += 1;
        }
        else {
            count -= 1;
        }
    }
    return major;
}

题目来源

Majority Element

求众数