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

排序题目:多数元素 II

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
      • 进阶
  • 前言
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法三
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:多数元素 II

出处:229. 多数元素 II

难度

3 级

题目描述

要求

给定大小为 n \texttt{n} n 的数组 nums \texttt{nums} nums,找出其中所有出现超过 ⌊ n 3 ⌋ \Big\lfloor \dfrac{\texttt{n}}{\texttt{3}} \Big\rfloor 3n 次的元素。

示例

示例 1:

输入: nums = [3,2,3] \texttt{nums = [3,2,3]} nums = [3,2,3]
输出: [3] \texttt{[3]} [3]

示例 2:

输入: nums = [1] \texttt{nums = [1]} nums = [1]
输出: [1] \texttt{[1]} [1]

示例 3:

输入: nums = [1,2] \texttt{nums = [1,2]} nums = [1,2]
输出: [1,2] \texttt{[1,2]} [1,2]

数据范围

  • n = nums.length \texttt{n} = \texttt{nums.length} n=nums.length
  • 1 ≤ n ≤ 5 × 10 4 \texttt{1} \le \texttt{n} \le \texttt{5} \times \texttt{10}^\texttt{4} 1n5×104
  • -10 9 ≤ nums[i] ≤ 10 9 \texttt{-10}^\texttt{9} \le \texttt{nums[i]} \le \texttt{10}^\texttt{9} -109nums[i]109

进阶

你可以使用线性时间复杂度和 O(1) \texttt{O(1)} O(1) 空间复杂度解决此问题吗?

前言

这道题是「多数元素」的进阶,要求找出数组中所有出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的元素。这道题也可以使用哈希表计数、排序和摩尔投票三种解法得到答案。

长度是 n n n 的数组中,最多有 2 2 2 个出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的元素。可以使用反证法证明。

假设有 3 3 3 个出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的元素,这 3 3 3 个元素的出现次数都不小于 ⌊ n 3 ⌋ + 1 \Big\lfloor \dfrac{n}{3} \Big\rfloor + 1 3n+1,因此这 3 3 3 个元素的总出现次数至少为 3 × ⌊ n 3 ⌋ + 3 3 \times \Big\lfloor \dfrac{n}{3} \Big\rfloor + 3 3×3n+3。由于 ⌊ n 3 ⌋ > n 3 − 1 \Big\lfloor \dfrac{n}{3} \Big\rfloor > \dfrac{n}{3} - 1 3n>3n1,因此 3 × ⌊ n 3 ⌋ + 3 > 3 × ( n 3 − 1 ) + 3 = 3 × n 3 − 3 + 3 = n 3 \times \Big\lfloor \dfrac{n}{3} \Big\rfloor + 3 > 3 \times (\dfrac{n}{3} - 1) + 3 = 3 \times \dfrac{n}{3} - 3 + 3 = n 3×3n+3>3×(3n1)+3=3×3n3+3=n,即这 3 3 3 个元素的总出现次数一定超过 n n n,和数组长度是 n n n 矛盾。因此数组中不可能有 3 3 3 个出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的元素,最多有 2 2 2 个出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的元素。

解法一

思路和算法

最直观的解法是统计数组中每个元素的出现次数,然后寻找出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的元素。

遍历数组,使用哈希表记录每个元素的出现次数,遍历结束之后即可得到数组中每个元素的出现次数。然后遍历哈希表,对于哈希表中的每个元素得到出现次数,将出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的元素添加到结果中。

代码

class Solution {public List<Integer> majorityElement(int[] nums) {Map<Integer, Integer> counts = new HashMap<Integer, Integer>();for (int num : nums) {counts.put(num, counts.getOrDefault(num, 0) + 1);}List<Integer> majorities = new ArrayList<Integer>();int n = nums.length;Set<Integer> set = counts.keySet();for (int num : set) {if (counts.get(num) > n / 3) {majorities.add(num);}}return majorities;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。遍历数组统计每个元素的出现次数需要 O ( n ) O(n) O(n) 的时间,遍历哈希表得到多数元素也需要 O ( n ) O(n) O(n) 的时间。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要创建哈希表记录每个元素的出现次数,哈希表中的元素个数不超过 n n n

解法二

思路和算法

首先将数组排序,排序后的数组满足相等的元素一定出现在数组中的相邻位置。如果一个元素在数组中的出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n,则排序后的数组中存在至少 ⌊ n 3 ⌋ + 1 \Big\lfloor \dfrac{n}{3} \Big\rfloor + 1 3n+1 个连续的元素都等于该元素,即一定存在两个差为 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的下标处的元素都等于该元素。

将数组 nums \textit{nums} nums 排序之后遍历数组 nums \textit{nums} nums,对于下标 i i i,当 i ≥ ⌊ n 3 ⌋ i \ge \Big\lfloor \dfrac{n}{3} \Big\rfloor i3n 时,如果 nums [ i ] = nums [ i − ⌊ n 3 ⌋ ] \textit{nums}[i] = \textit{nums}[i - \Big\lfloor \dfrac{n}{3} \Big\rfloor] nums[i]=nums[i3n],则 nums [ i ] \textit{nums}[i] nums[i] 是出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的元素。

为了避免重复计算,当 i < n − 1 i < n - 1 i<n1 nums [ i ] = nums [ i + 1 ] \textit{nums}[i] = \textit{nums}[i + 1] nums[i]=nums[i+1] 时跳过下标 i i i,只有当下标 i i i 的右侧没有与 nums [ i ] \textit{nums}[i] nums[i] 相等的元素时才判断 nums [ i ] = nums [ i − ⌊ n 3 ⌋ ] \textit{nums}[i] = \textit{nums}[i - \Big\lfloor \dfrac{n}{3} \Big\rfloor] nums[i]=nums[i3n] 是否成立,如果成立则将 nums [ i ] \textit{nums}[i] nums[i] 添加到结果中。

代码

class Solution {public List<Integer> majorityElement(int[] nums) {Arrays.sort(nums);List<Integer> majorities = new ArrayList<Integer>();int n = nums.length;for (int i = n / 3; i < n; i++) {int num = nums[i];if (i < n - 1 && num == nums[i + 1]) {continue;}if (num == nums[i - n / 3]) {majorities.add(num);}}return majorities;}
}

复杂度分析

  • 时间复杂度: O ( n log ⁡ n ) O(n \log n) O(nlogn),其中 n n n 是数组 nums \textit{nums} nums 的长度。排序需要 O ( n log ⁡ n ) O(n \log n) O(nlogn) 的时间。

  • 空间复杂度: O ( log ⁡ n ) O(\log n) O(logn),其中 n n n 是数组 nums \textit{nums} nums 的长度。排序需要 O ( log ⁡ n ) O(\log n) O(logn) 的递归调用栈空间。

解法三

思路和算法

原始的摩尔投票算法用于找到出现次数大于一半的元素,其时间复杂度是 O ( n ) O(n) O(n),空间复杂度是 O ( 1 ) O(1) O(1)。摩尔投票算法可以推广到寻找出现次数大于 ⌊ n k ⌋ \Big\lfloor \dfrac{n}{k} \Big\rfloor kn 的元素,其中 k k k 是大于 1 1 1 的正整数。

由于出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 的元素不可能超过 2 2 2 个,因此维护 2 2 2 个候选元素 majority 1 \textit{majority}_1 majority1 majority 2 \textit{majority}_2 majority2,以及两个候选元素的出现次数 count 1 \textit{count}_1 count1 count 2 \textit{count}_2 count2,初始时候选元素和出现次数都是 0 0 0

遍历数组,当遍历到元素 num \textit{num} num 时,执行如下操作。

  1. 比较 num \textit{num} num 是否和候选元素相等,如果相等则将相应的出现次数加 1 1 1

    1. 如果 num = majority 1 \textit{num} = \textit{majority}_1 num=majority1,则将 count 1 \textit{count}_1 count1 1 1 1

    2. 否则,如果 num = majority 2 \textit{num} = \textit{majority}_2 num=majority2,则将 count 2 \textit{count}_2 count2 1 1 1

  2. 如果 num \textit{num} num 和两个候选元素都不相等,则判断两个候选元素的出现次数是否为 0 0 0,如果为 0 0 0 则更新候选元素和出现次数。

    1. 如果 count 1 = 0 \textit{count}_1 = 0 count1=0,则将 majority 1 \textit{majority}_1 majority1 更新为 num \textit{num} num,并将 count 1 \textit{count}_1 count1 1 1 1

    2. 否则,如果 count 2 = 0 \textit{count}_2 = 0 count2=0,则将 majority 2 \textit{majority}_2 majority2 更新为 num \textit{num} num,并将 count 2 \textit{count}_2 count2 1 1 1

  3. 如果 num \textit{num} num 和两个候选元素都不相等且两个候选元素的出现次数都大于 0 0 0,则 num \textit{num} num 和两个候选元素抵消,将 count 1 \textit{count}_1 count1 count 2 \textit{count}_2 count2 都减 1 1 1

遍历结束之后,得到两个候选元素。再次遍历数组,统计两个候选元素在数组中的出现次数,当出现次数大于 ⌊ n 3 ⌋ \Big\lfloor \dfrac{n}{3} \Big\rfloor 3n 时将候选元素添加到结果中。

代码

class Solution {public List<Integer> majorityElement(int[] nums) {int majority1 = 0, majority2 = 0;int count1 = 0, count2 = 0;for (int num : nums) {if (num == majority1) {count1++;} else if (num == majority2) {count2++;} else if (count1 == 0) {majority1 = num;count1++;} else if (count2 == 0) {majority2 = num;count2++;} else {count1--;count2--;}}count1 = 0;count2 = 0;for (int num : nums) {if (num == majority1) {count1++;} else if (num == majority2) {count2++;}}List<Integer> majorities = new ArrayList<Integer>();int n = nums.length;if (count1 > n / 3) {majorities.add(majority1);}if (count2 > n / 3) {majorities.add(majority2);}return majorities;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要遍历数组 nums \textit{nums} nums 两次。

  • 空间复杂度: O ( 1 ) O(1) O(1)

相关文章:

排序题目:多数元素 II

文章目录 题目标题和出处难度题目描述要求示例数据范围进阶 前言解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 解法三思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;多数元素 II 出处&#xff1a;229. 多数元素 II 难度 3 级 题目描述 …...

<电力行业> - 《第1课:电力行业的五大四小》

1 什么是电力行业的五大四小&#xff1f; 我们常说的电力行业的五大四小&#xff0c;指的是电力行业有实力的公司&#xff0c;分为&#xff1a;较强梯队的五大集团、较弱梯队的四小豪门。 五个实力雄厚的集团&#xff0c;分别是&#xff1a; 中国华能集团公司中国大唐集团公…...

数据库定义语言(DDL)

数据库定义语言&#xff08;DDL&#xff09; 一、数据库操作 1、 查询所有的数据库 SHOW DATABASES;效果截图&#xff1a; 2、使用指定的数据库 use 2403 2403javaee;效果截图&#xff1a; 3、创建数据库 CREATE DATABASE 2404javaee;效果截图&#xff1a; 4、删除数据…...

mybatis实现多表查询

mybatis高级查询【掌握】 1、准备工作 【1】包结构 创建java项目&#xff0c;导入jar包和log4j日志配置文件以及连接数据库的配置文件&#xff1b; 【2】导入SQL脚本 运行资料中的sql脚本&#xff1a;mybatis.sql 【3】创建实体来包&#xff0c;导入资料中的pojo 【4】User…...

数据结构:队列详解 c++信息学奥赛基础知识讲解

目录 一、队列概念 二、队列容器 三、队列操作 四、代码实操 五、队列遍历 六、案例实操 题目描述&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 详细代码&#xff1a; 一、队列概念 队列是一种特殊的线性…...

硬件开发笔记(二十三):贴片电阻的类别、封装介绍,AD21导入贴片电阻原理图封装库3D模型

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/140110514 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…...

Kafka基本原理详解

&#xff08;一&#xff09;概念理解 Apache Kafka是一种开源的分布式流处理平台&#xff0c;专为高性能、高吞吐量的实时数据处理而设计。它最初由LinkedIn公司开发&#xff0c;旨在解决其网站活动中产生的大量实时数据处理和传输问题&#xff0c;后来于2011年开源&#xff0…...

【Unity】RPG2D龙城纷争(七)关卡编辑器之剧情编辑

更新日期:2024年7月1日。 项目源码:第五章发布(正式开始游戏逻辑的章节) 索引 简介一、剧情编辑1.对话数据集2.对话触发方式3.选择对话角色4.设置对话到关卡5.通关条件简介 严格来说,剧情编辑不在关卡编辑器界面中完成,只不过它仍然属于关卡编辑的范畴。 在我们的设想中…...

uniapp启动页面鉴权页面闪烁问题

在使用uni-app开发app 打包完成后如果没有token&#xff0c;那么就在onLaunch生命周期里面判断用户是否登录并跳转至登录页。 但是在app中页面会先进入首页然后再跳转至登录页&#xff0c;十分影响体验。 处理方法&#xff1a; 使用plus.navigator.closeSplashscreen() 官网…...

全志H616交叉编译工具链的安装与使用

交叉编译的概念 1. 什么是交叉编译&#xff1f; 交叉编译是指在一个平台上生成可以在另一个平台上运行的可执行代码。例如&#xff0c;在Ubuntu Linux上编写代码&#xff0c;并编译生成可在Orange Pi Zero2上运行的可执行文件。这个过程是通过使用一个专门的交叉编译工具链来…...

深入解析Java和Go语言中String与byte数组的转换原理

1.Java String与byte[]互相转换存在的问题 java中&#xff0c;按照byte[] 》string 》byte[]的流程转换后&#xff0c;byte数据与最初的byte不一致。 多说无益&#xff0c;上代码&#xff0c;本地macos机器执行&#xff0c;统一使用的UTF-8编码。 import java.nio.charset.S…...

什么是strcmp函数

目录 开头1.什么是strcmp函数2.strcmp函数里的内部结构3.strcmp函数的实际运用(这里只列举其一)脑筋急转弯 结尾 开头 大家好&#xff0c;我叫这是我58。今天&#xff0c;我们要来认识一下C语言中的strcmp函数。 1.什么是strcmp函数 strcmp函数来自于C语言中的头文件<str…...

Follow Carl To Grow|【LeetCode】491.递增子序列,46.全排列,47.全排列 II

【LeetCode】491.递增子序列 题意&#xff1a;给你一个整数数组 nums &#xff0c;找出并返回所有该数组中不同的递增子序列&#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素&#xff0c;如出现两个整数相等&#xff0c;也可以…...

pytorch nn.Embedding 用法和原理

nn.Embedding 是 PyTorch 中的一个模块&#xff0c;用于将离散的输入&#xff08;通常是词或子词的索引&#xff09;映射到连续的向量空间。它在自然语言处理和其他需要处理离散输入的任务中非常常用。以下是 nn.Embedding 的用法和原理。 用法 初始化 nn.Embedding nn.Embed…...

Python中常用的有7种值(数据)的类型及type()语句的用法

目录 0.Python中常用的有7种值&#xff08;数据&#xff09;的类型Python中的数据类型主要有&#xff1a;Number&#xff08;数字&#xff09;、Boolean&#xff08;布尔&#xff09;、String&#xff08;字符串&#xff09;、List&#xff08;列表&#xff09;、Tuple&#xf…...

某配送平台未授权访问和弱口令(附赠nuclei默认密码验证脚本)

找到一个某src的子站&#xff0c;通过信息收集插件&#xff0c;发现ZABBIX-监控系统&#xff0c;可以日一下 使用谷歌搜索历史漏洞&#xff1a;zabbix漏洞 通过目录扫描扫描到后台&#xff0c;谷歌搜索一下有没有默认弱口令 成功进去了&#xff0c;挖洞就是这么简单 搜索文章还…...

01.总览

目录 简介Course 1: Natural Language Processing with Classification and Vector SpaceWeek 1: Sentiment Analysis with Logistic RegressionWeek 2: Sentiment Analysis with Nave BayesWeek 3: Vector Space ModelsWeek 4: Machine Translation and Document Search Cours…...

Linux换源

前言 安装完Linux系统&#xff0c;尽量更换源以提高安装软件的速度。 步骤 备份原始源列表sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak修改sources.list sudo vim /etc/apt/sources.list将内容替换成对应的源 **PS&#xff1a;清华源地址&#xff1a;https:…...

【高考志愿】 化学工程与技术

目录 一、专业概述 二、就业前景 三、就业方向 四、报考注意 五、专业发展与深造 六、化学工程与技术专业排名 七、总结 一、专业概述 化学工程与技术专业&#xff0c;这是一门深具挑战与机遇的综合性学科。它融合了工程技术的实用性和化学原理的严谨性&#xff0c;为毕…...

2024上半年网络与数据安全法规政策、国标、报告合集

事关大局&#xff0c;我国数据安全立法体系已基本形成并逐步细化。数据基础制度建设事关国家发展和安全大局&#xff0c;数据安全治理贯穿构建数据基础制度体系全过程。随着我国数字经济建设进程加快&#xff0c;数据安全立法实现由点到面、由面到体加速构建&#xff0c;目前已…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

【java面试】微服务篇

【java面试】微服务篇 一、总体框架二、Springcloud&#xff08;一&#xff09;Springcloud五大组件&#xff08;二&#xff09;服务注册和发现1、Eureka2、Nacos &#xff08;三&#xff09;负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程

基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...

Python第七周作业

Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt&#xff0c;并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径&#xff0c;并创建logs目录&#xff08;若不存在&#xff09; 3.递归遍历目录data&#xff0c;输出所有.csv文件的路径…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录

#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...