LeetCode之169题多数元素

算法

发布日期: 2021-07-09

来源：力扣（LeetCode）https://leetcode-cn.com/problems/majority-element

题目

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例1：

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

示例2：

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

示例3：

输入：[1]
输出：1

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

Java版

简单解法，基于哈希表实现

时间和空间复杂度都为O(n)；算法原理：即遍历整个数组，统计元素个并放到哈希表中，如果出现数量超过一半时就可以直接返回了。

public int majorityElement(int[] nums) {
    int max = nums.length / 2;
    Map<Integer, Integer> map = new HashMap<>();
    for(int num:nums){
        Integer val = map.get(num);
        if(null==val){
            val = 1;
        }else{
            val++;
            if(val > max){
                return num;
            }
        }
        map.put(num, val);
    }
    return nums[0];
}

通过排序解决

根据题目对多数元素的定义，其数量是超过一半的，那么排序后的数组中，多数元素一定是占一半以上的，那么无论顺序如何中间的值一定是最多元素。

public int majorityElement(int[] nums) {
    Arrays.sort(nums);// 时间复杂度 n*log(n)
    return nums[nums.length >> 1];
}

计数（摩尔投票法）

候选人(candidate)初始化为nums[0]，票数(count)初始化为1；当遇到的数和候选人(candidate)相同时，则票数加1，否则票数减1；若票数为0时则更换候选人，票数重置为1。遍历完数组，最终的候选人就是结果。

为什么？因为多数元素至少有⌊ n/2 + 1⌋个元素，所以最终可以一一抵消每个数，最后剩下的一定是多数元素。

public int majorityElement(int[] nums) {
    int count = 1;
    int candidate = nums[0];

    for(int i=1; i<nums.length; i++){
        if(candidate==nums[i]){
            count++;
        }else{
            if(--count == 0){
                candidate = nums[i];
                count = 1;
            }
        }
    }
    return candidate;
}