LeetCode之169题多数元素


来源:力扣(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;
}

特别提醒:扫码关注微信订阅号'起岸星辰',实时掌握IT业界技术资讯! 转载请保留原文中的链接!
 上一篇
Java单元测试实战 Java单元测试实战
我们在开发中不可避免的要对自己写的代码进行单元测试,下面就来看看开发中常用到的单元测试以及和mock的搭配使用的示例。
2021-07-15
下一篇 
Spring-Cloud之Hystrix Spring-Cloud之Hystrix
Hystrix是Netflix旗下的一个延迟和容错库,旨在隔离对远程系统、服务和第三方库的访问,停止级联故障并在故障不可避免的复杂分布式系统中启用弹性配置。
2021-06-22
  目录