LeetCode169-Majority Element

题目

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.

分析

题意是找出一个数组中数量超过一半的那个数来。第一种容易想到的思路是利用HashMap统计,通过遍历该数组统计每个字符出现的次数,然后遍历HashMap取出次数最大者返回。但这种方法耗费空间较大,且需两次线性遍历,时间空间复杂度都较大。

另一种更巧妙的方法是用到“投票算法”。我们可以想到一种抵消的策略,既然有一个数出现了一半以上的次数,那么它一个人的量就比其他所有数的量还多,也就是说其他数与它相抵,最终剩余的结果一定还是它。那么思路就有了:我们需要设立一个count变量作为抵消用,一个cur变量记录当前数量最大的元素用,每当访问一个元素时,率先判断它是否和cur相等,若是则count++,否则证明是一个相异的元素,这时count- -,当count被减到0的时候,说明cur元素与其它之前访问过的所有元素的量相同了,此时如果又出现一个相异元素,那么count将++,直到之后被数量最多的那个数占领以后,cur就变为了所求。

但需注意的是,能使用这种方法的前提是,出现次数最多的这个数一定是要严格大于数组元素的一半的:

  • 若n为基数,那么好说,它的数量一定 >= (n + 1) / 2。
  • 若n为偶数,则数量一定也要>= n / 2 + 1,为什么要+1呢?因为一种最极端的情况是,假若数组中只有两个数,各占一半,且前面一半是第一个数,后面一半是第二个数,那么此时当第二个数抵消完前面第一个数的count时,尽管count = 0了,但cur并没有得到更新,退出循环后,cur返回的则是第一个数的值了。也就是说cur返回的数值与前面一半是哪个数正相关!那如果前面一半是a答案就是a,前面一半是b答案就是b,这导致了算法的不确定性,故是错误的。

代码

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 1;
        int cur = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            
            if (count == 0) {
                cur = nums[i];
                count++;
            } else {
                if (nums[i] != cur) count--;
                else count++;
            }
        }
        
        return cur;
    }
}

Leave a Comment.