当前位置: 首页 > 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;目前已…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...