当前位置: 首页 > article >正文

力扣Hot100——169. 多数元素

在这里插入图片描述

  1. 解法1:使用HashMap
    将nums数组映射到HashMap中,键为nums的值,值为nums中值的数量;
    然后遍历哈希表,返回值最大的键

    class Solution {
        private Map<Integer, Integer> countNums(int[] nums) {
            Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
            for (int num : nums) {
                if (!counts.containsKey(num)) {
                    counts.put(num, 1);
                } else {
                    counts.put(num, counts.get(num) + 1);
                }
            }
            return counts;
        }
    
    	public int majorityElement(int[] nums) {
            Map<Integer, Integer> counts = countNums(nums);
    
            Map.Entry<Integer, Integer> majorityEntry = null;
            for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
                if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                    majorityEntry = entry;
                }
            }
    
            return majorityEntry.getKey();
        }
    }
    

    作者:力扣官方题解
    链接:https://leetcode.cn/problems/majority-element/solutions/146074/duo-shu-yuan-su-by-leetcode-solution/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  2. 解法2:由于众数数量超过n/2,并且众数一定存在,那么排序后的中间位置的值一定是众数

    // 排序取中位值
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
    
  3. 解法3:Boyer-Moore 投票算法
    首先明白一点:将众数标记为 +1,非众数标记为 -1,遍历所有数值后,众数的和一定是大于零的,因为众数有过半的票数。
    这就像是进行总统选举,我们维护一个总统候选人 candidate ,以及一个 candidate 的票数 count。当遍历选票时,第一次我们将第一张票作为 candidate 的值,然后遍历,遇到相同的票 count +1,否则 -1,当 count == 0,就将下一张票作为候选人 candidate,如此遍历至最后,candidate 的 count != 0的 candidate一定是票数最多的 candidate,也就是所有票中的众数。(原因就是上面的众数 + 非众数 count 结果一定大于零)

    class Solution {
    	
    	public int majorityElement(int[] nums){
    		int candidate = 0;
    		int count = 0;
    		
    		for(int num : nums){
    			if(count == 0){
    				candidate = num;
    			}
    			// 这行代码绝了
    			count +=  (candidate == num) ? +1 : -1;
    		}
    		return candidate;
    	}
    }
    

    这行代码绝了!!!count += (candidate == num) ? +1 : -1;

关于解法 3 还有一个很好理解的解释,来自于力扣kxACE转发的 youtube 视频,称为同归于尽消杀法

由于多数超过50%, 比如100个数,那么多数至少51个,剩下少数是49个。
遍历数组

  1. 第一个到来的士兵,直接插上自己阵营的旗帜占领这块高地,此时领主 winner 就是这个阵营的人,现存兵力 count = 1。
  2. 如果新来的士兵和前一个士兵是同一阵营,则集合起来占领高地,领主不变,winner 依然是当前这个士兵所属阵营,现存兵力 count 加一;
  3. 如果新来到的士兵不是同一阵营,则前方阵营派一个士兵和它同归于尽
    此时前方阵营兵力-1, 即使双方都死光,这块高地的旗帜 winner 不变,没有可以去换上自己的新旗帜。
  4. 当下一个士兵到来,发现前方阵营已经没有兵力,新士兵就成了领主,winner 变成这个士兵所属阵营的旗帜,现存兵力 count ++。
    就这样各路军阀一直厮杀以一敌一同归于尽的方式下去,直到少数阵营都死光,剩下几个必然属于多数阵营的,winner 是多数阵营。

(多数阵营 51个,少数阵营只有49个,死剩下的2个就是多数阵营的人)


http://www.kler.cn/a/590614.html

相关文章:

  • OSPF与RIP联动实验
  • GStreamer —— 3.1、Qt+GStreamer制作多功能播放器,支持本地mp4文件、rtsp流、usb摄像头等(可跨平台,附源码)
  • 如何高效安装和配置WordPress:从基础依赖到高级设置
  • GaussDB分布式集群数据库创建database
  • 目标检测任务,如何区分两个相近似的目标
  • QT | 信号与槽(超详解)
  • 高级java每日一道面试题-2025年3月03日-微服务篇[Eureka篇]-Eureka自我保护机制是什么?
  • 安卓,高效文件管理与逆向修改的完美工具
  • 【java零碎知识点】------返回值类型的大小排序
  • 工程化与框架系列(36)--前端监控告警实践
  • SpringMVC(八)Knife4j 接口文档
  • Anaconda 入门指南
  • 在群晖DS923+手动安装我Wordpress最新版
  • 定义模型生成数据表
  • rust 中的package、crate、module
  • python打印输出到文件
  • Go Ebiten小游戏开发:2048
  • Qt5.15.2实现Qt for WebAssembly与示例
  • 学习单片机需要多长时间才能进行简单的项目开发?
  • 04 1个路由器配置一个子网的dhcp服务