力扣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.rhkb.cn/news/35070.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

EasyRTC嵌入式音视频通话SDK:微信生态支持、轻量化架构与跨平台兼容性(Linix/Windows/ARM/Android/iOS/LiteOS)

随着WebRTC技术的不断发展&#xff0c;实时音视频通信在各个领域的应用越来越广泛。EasyRTC嵌入式音视频通话SDK作为一款基于WebRTC技术的实时通信解决方案&#xff0c;凭借其强大的功能和灵活的集成能力&#xff0c;受到了越来越多开发者的关注。 一、系统架构设计 纯C语言开…

QuickAPI:一键将 Excel 数据转为数据库表

在开发和数据管理中&#xff0c;将 Excel 数据快速导入数据库是一项常见需求&#xff0c;但手动建表和导入的过程往往让人头疼。 QuickAPI 作为一款高效的统一数据服务平台&#xff0c;提供了一键将 Excel 数据转为数据库表的功能&#xff0c;极大简化了操作流程。本文将以技术…

【MySQL】多表查询(笛卡尔积现象,联合查询、内连接、左外连接、右外连接、子查询)-通过练习快速掌握法

在DQL的基础查询中&#xff0c;我们已经学过了多表查询的一种&#xff1a;联合查询&#xff08;union&#xff09;。本文我们将系统的讲解多表查询。 笛卡尔积现象 首先&#xff0c;我们想要查询emp表和stu表两个表&#xff0c;按照我们之前的知识栈&#xff0c;我们直接使用…

JavaScript如何做类型转换

一、类型转换 二、补充 console.log(1 "2" "2"); // 122 console.log(1 "2" "2"); // 32 console.log(1 -"1" "2"); // 02 console.log("1" "1" "2"); // 112 consol…

华为中小型企业项目案例

实验目的(1) 熟悉华为交换机和路由器的应用场景 (2) 掌握华为交换机和路由器的配置方法 实验拓扑实验拓扑如图所示。 华为中小型企业项目案例拓扑图 实验配置市场部和技术部的配置创建VLANLSW1的配置 [LSW1]vlan batch 10 20 [LSW1]q…

【PyTorch][chapter-35][MLA]

前言&#xff1a; MLA&#xff08;Multi-head Latent Attention&#xff0c;多头潜在注意力&#xff09;旨在提高推理效率和降低计算资源的消。MLA的核心思想在于通过信息转移来优化KV缓存的使用 MLA的技术特点主要包括&#xff1a; KV压缩与潜在变量&#xff1a;将键&#xff…

Spring Cloud 中的服务注册与发现: Eureka详解

1. 背景 1.1 问题描述 我们如果通过 RestTamplate 进行远程调用时&#xff0c;URL 是写死的&#xff0c;例如&#xff1a; String url "http://127.0.0.1:9090/product/" orderInfo.getProductId(); 当机器更换或者新增机器时&#xff0c;这个 URL 就需要相应地变…

微服务存在的问题及解决方案

微服务存在的问题及解决方案 1. 存在问题 1.1 接口拖慢 因为一个接口在并发时&#xff0c;正好执行时长又比较长&#xff0c;那么当前这个接口占用过多的 Tomcat 连接&#xff0c;导致其他接口无法即时获取到 Tomcat 连接来完成请求&#xff0c;导致接口拖慢&#xff0c;甚至…

centos 安装pip时报错 Cannot find a valid baseurl for repo: centos-sclo-rh/x86_64

centos 安装pip时报错 [rootindex-es app-ai]# yum update Loaded plugins: fastestmirror Repository centos-sclo-rh is listed more than once in the configuration Determining fastest mirrors Could not retrieve mirrorlist http://mirrorlist.centos.org?archx86_64…

解决图片转 ICO 图标难题,支持批量处理

还在为图片转 ICO 图标发愁吗&#xff1f;别担心&#xff0c;今天为大家带来一款超实用的工具 ——Any to Icon。它功能强大&#xff0c;可实现批量图片转 ICO 图标&#xff0c;轻松解决格式转换难题。更棒的是&#xff0c;这款工具极为小巧&#xff0c;无需安装&#xff0c;即…

MultiPost--多平台博客发布工具

网站介绍 一键发布内容到多个社交平台的浏览器插件&#xff0c;支持知乎、微博、小红书、抖音等主流平台&#xff0c;支持文字、图片、视频等内容形式. 地址 GitHub &#xff1a; https://github.com/leaper-one/MultiPost-Extension Chorme: https://chromewebstore.google.…

Linux进程状态详解:僵尸进程与孤儿进程的深度探索与实践

文章目录 前言一、进程状态概述1.1 运行状态1.2 阻塞状态1.3 挂起状态 二、具体的Linux操作系统中的进程状态2.1 Linux内核源代码2.2 查看进程状态2.3 D磁盘休眠状态(Disk sleep)D状态的定义&#xff1a; 2.4 T停止状态(stopped)停止状态的概述&#xff1a;停止状态的触发条件&…

【Linux】深入理解进程和文件及内存管理

个人主页~ 深入理解进程和文件及内存管理 一、重谈Linux下一切皆文件二、操作系统对物理内存的管理1、物理内存与磁盘的数据交互2、操作系统对物理内存的管理 三、文件页缓冲区向文件写入数据的过程 四、动态库是如何被加载的关于动态库中的全局变量 五、深入理解地址1、程序地…

★9.4.2 context2D 绘图

返回目录&#xff1a; Qt QML专栏目录结构_qml 项目 目录-CSDN博客 ★9.4.2 context2D 绘图 Object <- context 属性 canvas : QtQuick::Canvas fillRule : enumeration fillStyle : variant fillStyle: 设置或获取当前填充颜色或样式。 font : string g…

汇编基础知识

CPU&#xff1a;一种可以执行机器指令进行运算的芯片&#xff08;微处理器&#xff09;。 存储器&#xff08;内存&#xff09;&#xff1a;存放CPU可以工作的指令和数据&#xff08;指令和数据都是二进制信息&#xff09;。 磁盘不同于内存&#xff0c;磁盘中的数据要读到内…

1536数字三角形

1536数字三角形 ⭐️难度&#xff1a;中等 &#x1f31f;考点&#xff1a;动态规划 &#x1f4d6; &#x1f4da; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;public class Main {public static void main(…

基于VMware的虚拟机集群搭建

本文作者&#xff1a; slience_me 文章目录 基于VMware的虚拟机集群搭建1. 安装Vmware2. 构建虚拟机3. 安装Linux4. 网络配置5. 开始克隆6. 初始化系统6.1 开放root账户6.2 SSH服务6.3 设置静态IP6.4 镜像源 host 主机名 基于VMware的虚拟机集群搭建 该集群采用镜像ubuntu-20.0…

windows平台搭建python环境

python语言 Python 是一种高级、解释型、跨平台的编程语言&#xff0c;由Guido van Rossum于1991年设计&#xff0c;并发展成为全球最受欢迎的编程语言之一。它以简单易读的语法、灵活的特性和丰富的标准库闻名&#xff0c;适合初学者和经验丰富的开发者。 Python 支持多种编…

【系统架构设计师】操作系统 - 文件管理 ② ( 位示图 | 空闲区域 管理 | 位号 | 字号 )

文章目录 一、空闲区域 管理1、空闲区域分配2、空闲区域 管理方式 简介 二、位示图 简介1、位示图 表示2、位示图 字号3、位示图 位号4、位示图 中 比特位 分组管理 三、位示图 考点1、计算磁盘 位示图 的大小2、位示图 位置计算 一、空闲区域 管理 1、空闲区域分配 在 索引文件…

SpringData Redis:RedisTemplate配置与数据操作

文章目录 引言一、Redis概述与环境准备二、RedisTemplate基础配置三、连接属性配置四、操作String类型数据五、操作Hash类型数据六、操作List类型数据七、操作Set类型数据八、操作ZSet类型数据九、事务与管道操作总结 引言 Redis作为高性能的NoSQL数据库&#xff0c;在分布式系…