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

LeetCode 热题 100_多数元素(97_169_简单_C++)(哈希表;排序)

LeetCode 热题 100_多数元素(97_169_简单_C++)

    • 题目描述:
    • 输入输出样例:
    • 题解:
      • 解题思路:
        • 思路一(哈希表):
        • 思路二(排序):
      • 代码实现
        • 代码实现(思路一(哈希表)):
        • 代码实现(思路二(排序)):
        • 以思路二为例进行调试

题目描述:

给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

输入输出样例:

示例 1:
输入:nums = [3,2,3]
输出:3

示例 2:
输入:nums = [2,2,1,1,1,2,2]
输出:2

提示:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

题解:

解题思路:

思路一(哈希表):

1、我们通过数组中出现次数 大于 ⌊ n/2 ⌋ 的元素只能为一个,推断出答案只有一个元素(给定的数组总是存在多数元素)。则我们可以使用哈希表对每个元素进行计数,记录其中出现次数最大的元素。
2、复杂度分析:
① 时间复杂度:O(n),其中 n 是数组的长度,只遍历了一遍数组。
② 空间复杂度:O(n),哈希表所使用的空间。

思路二(排序):

1、当我们对数组进行排序后,出现次数最大的元素会聚集在一起,且大于n/2,所以取中间元素则为出现次数最大的元素。

2、复杂度分析
① 时间复杂度:O(n log n),快排。
② 空间复杂度:O(log n),快排使用的空间。

代码实现

代码实现(思路一(哈希表)):
class Solution1 {
public:// 该函数返回数组中出现次数最多的元素int majorityElement(vector<int> &nums) {int max_frequency = 0; // 存储最大出现次数int most_frequent_element; // 存储出现次数最多的元素unordered_map<int, int> mp; // 用哈希表存储每个元素的出现次数// 遍历数组for (auto &i : nums) {mp[i]++; // 增加当前元素的出现次数if (mp[i] > max_frequency) { // 如果当前元素的出现次数大于当前最大次数max_frequency = mp[i]; // 更新最大出现次数most_frequent_element = i; // 更新出现次数最多的元素}}return most_frequent_element; // 返回出现次数最多的元素}
};
代码实现(思路二(排序)):
class Solution2 {
public:// 该函数返回数组中出现次数最多的元素int majorityElement(vector<int> &nums) {//快速排序sort(nums.begin(),nums.end());return nums[nums.size()/2]; // 返回出现次数最多的元素}
};
以思路二为例进行调试
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;class Solution2 {
public:// 该函数返回数组中出现次数最多的元素int majorityElement(vector<int> &nums) {//快速排序sort(nums.begin(),nums.end());return nums[nums.size()/2]; // 返回出现次数最多的元素}
};int main(int argc, char const *argv[])
{vector<int> nums={3,3,4};Solution2 s;cout<<s.majorityElement(nums);return 0;
}

LeetCode 热题 100_多数元素(97_169)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

相关文章:

LeetCode 热题 100_多数元素(97_169_简单_C++)(哈希表;排序)

LeetCode 热题 100_多数元素&#xff08;97_169_简单_C&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;哈希表&#xff09;&#xff1a;思路二&#xff08;排序&#xff09;&#xff1a; 代码实现代码实现&…...

【C++】【设计模式】生产者-消费者模型

生产者-消费者模型&#xff08;Producer-Consumer Model&#xff09;是一种经典的并发编程模式&#xff0c;用于解决多线程或多进程环境下的数据共享和任务协作问题。以下是对该模型的详细介绍&#xff1a; 一、核心概念 生产者&#xff08;Producer&#xff09;&#xff1a;…...

第五十七篇 Java接口设计之道:从咖啡机到智能家居的编程哲学

目录 引言&#xff1a;生活中的接口无处不在一、咖啡机与基础接口&#xff1a;理解抽象契约1.1 咖啡制作的标准接口 二、智能家居与策略模式&#xff1a;灵活切换实现2.1 温度调节策略场景 三、物流系统与工厂模式&#xff1a;标准接口下的多样实现3.1 快递运输接口设计 四、健…...

centos9安装docker 配置docker代理

设置docker库 sudo dnf -y install dnf-plugins-core sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo 安装 Docker 包 sudo dnf install docker-ce docker-ce-cli containerd.io docker-buildx-plugin docker-compose-plugin …...

OpenAI for Countries:全球AI基础设施的“技术基建革命”

2025年5月7日&#xff0c;OpenAI宣布启动“OpenAI for Countries”计划&#xff0c;目标是为全球各国构建本土化的AI基础设施&#xff0c;提供定制化服务。这一计划被视为其“星际之门”项目的全球化延伸&#xff0c;以技术合作为核心&#xff0c;覆盖数据中心建设、模型适配与…...

手风琴效果

图示&#xff1a; 目的&#xff1a;这段HTML代码展示了一个简单的图片展示效果。通过使用Flexbox布局&#xff0c;创建了一个包含多个图片的容器&#xff0c;每张图片的宽度默认为120px&#xff0c;并在鼠标悬停时扩展至400px。代码中&#xff0c;图片路径通过JavaScript动态生…...

idea Maven 打包SpringBoot可执行的jar包

背景&#xff1a;当我们需要坐联调测试的时候&#xff0c;需要对接前端同事&#xff0c;则需要打包成jar包直接运行启动服务 需要将项目中的pom文件增加如下代码配置&#xff1a; <build><plugins><plugin><groupId>org.springframework.boot</gr…...

Visual Studio 项目 .gitignore 文件指南

Visual Studio 项目 .gitignore 文件指南 什么是 .gitignore&#xff1f; .gitignore 是一个特殊的文件&#xff0c;用于告诉 Git 哪些文件或文件夹不需要纳入版本控制。这对于 Visual Studio 项目尤其重要&#xff0c;因为 Visual Studio 会生成很多你不需要手动管理的文件。…...

使用ADB命令操作Android的apk/aab包

keystore文件转换jks文件 操作步骤&#xff1a; 步骤1&#xff0c;生成P12文件&#xff1a; keytool -importkeystore -srckeystore [文件名].keystore -srcstoretype JKS -deststoretype PKCS12 -destkeystore [文件名].p12 步骤2&#xff0c;生成jks文件&#xff1a; keytool…...

Ansys 计算刚柔耦合矩阵系数

Ansys 计算刚柔耦合系数矩阵 文章目录 Ansys 计算刚柔耦合系数矩阵卫星的刚柔耦合动力学模型采用 ANSYS 的 APDL 语言的计算方法系统转动惯量的求解方法参考文献 卫星的刚柔耦合动力学模型 柔性航天器的刚柔耦合动力学模型可以表示为 m v ˙ B t r a n η F J ω ˙ ω J…...

原生小程序+springboot+vue医院医患纠纷管理系统的设计与开发(程序+论文+讲解+安装+售后)

感兴趣的可以先收藏起来&#xff0c;还有大家在毕设选题&#xff0c;项目以及论文编写等相关问题都可以给我留言咨询&#xff0c;我会一一回复&#xff0c;希望帮助更多的人。 系统背景 在医疗行业快速发展的当下&#xff0c;医患关系已成为社会各界关注的焦点。近年来&#…...

django扩展练习记录

一、Django 中使用 django-apscheduler 实现定时任务 可以方便地管理周期性任务&#xff08;如每天清理缓存、定时发送邮件等&#xff09; 1. 安装 pip install django-apscheduler -i https://pypi.tuna.tsinghua.edu.cn/simple #0.7.02.添加到应用&#xff0c;python m…...

Android Exoplayer多路不同时长音视频混合播放

在上一篇Android Exoplayer 实现多个音视频文件混合播放以及音轨切换中我们提到一个问题&#xff0c;如果视频和音频时长不一致&#xff0c;特别是想混合多个音频和多个视频时就会出问题&#xff0c;无法播放。报错如下&#xff1a; E/ExoPlayerImplInternal(11191): Playback…...

第一章:HTML基石·现实的骨架

教学目标&#xff1a; • 理解 HTML 的整体结构&#xff08;<!DOCTYPE>, <html>,<head>, <body>&#xff09; • 掌握基础标签&#xff08;<h1>, <p>, <a>, <img>, <ul>/<ol>/<li>, <div>, <span&…...

按键精灵ios脚本新增元素功能助力辅助工具开发(二)

元素节点功能&#xff08;iOSElement&#xff09;​ 在按键精灵 iOS 新版 APP v2.2.0 中&#xff0c;新增了元素节点功能 iOSElement&#xff0c;该功能包含共 15 个函数。这一功能的出现&#xff0c;为开发者在处理 iOS 应用界面元素时提供了更为精准和高效的方式。通过这些函…...

【源码+文档+调试讲解】党员之家服务系统小程序1

摘 要 本毕业设计的内容是设计并且实现一个基于springboot的党员之家服务系统小程序。它是在Windows下&#xff0c;以MYSQL为数据库开发平台&#xff0c;java技术和Tomcat网络信息服务作为应用服务器。党员之家服务系统小程序的功能已基本实现&#xff0c;主要包括首页、个人…...

《ffplay 读线程与解码线程分析:从初始化到 seek 操作,对比视频与音频解码的差异》

1 read-thread 1.1 初始化部分 1.分配. avformat_alloc_context 创建上下⽂ ic avformat_alloc_context();if (!ic) {av_log(NULL, AV_LOG_FATAL, "Could not allocate context.\n");ret AVERROR(ENOMEM);goto fail;}2 ic->interrupt_callback.callback deco…...

AI+可视化:数据呈现的未来形态

当AI生成的图表开始自动“美化”数据&#xff0c;当动态可视化报告能像人类一样“讲故事”&#xff0c;当你的眼球运动直接决定数据呈现方式——数据可视化的未来形态&#xff0c;正在撕裂传统认知。某车企用AI生成的3D可视化方案&#xff0c;让设计师集体失业&#xff1b;某医…...

Spring Boot 整合 Redis 实战

一、整合准备&#xff1a;环境与依赖​ 1. 技术栈说明​ Spring Boot 版本&#xff1a;3.1.2&#xff08;兼容 Java 17&#xff09;​ Redis 服务器&#xff1a;Redis 7.0&#xff08;本地部署或 Docker 容器&#xff09;​ Maven 依赖&#xff1a; <dependency><…...

pdf url 转 图片

背景&#xff1a;vue2.0需要把pdf转成图片&#xff0c;显示在url里面&#xff0c;使用pdfjs-dist来解决 步骤&#xff1a; 1、安装依赖包(我的项目是node12&#xff0c;安装太高版本会报错) npm i pdfjs-dist2.16.105 2、vue代码 <template><div class"main…...

JPG与PDF格式转换器

该插件可实现JPG与PDF格式的互转。 MainForm.Designer.cs using System.Windows.Forms; namespace JpgToPdfConverter {partial class MainForm{private System.ComponentModel.IContainer components null;protected override void Dispose(bool disposing){if (disposing &…...

Kafka 如何保证消息顺序性

文章目录 分区策略轮询随机按 Partition 路由按 key 路由 顺序性保证 分区策略 Kafka 的消息会被生产者发送到分区 Partition中&#xff0c;然后消费者通过获取分区中的消息来完成消费操作。所以Kafka不仅有主题 Topic这个概念&#xff0c;也引入分区 Partition 这个概念来实现…...

C++23 views::zip 和 views::zip_transform (P2321R2) 深入解析

文章目录 一、引言二、C23与Ranges库背景知识2.1 C23概述2.2 Ranges库回顾 三、views::zip 详解3.1 功能与定义3.2 使用场景3.3 示例代码 四、views::zip_transform 详解4.1 功能与定义4.2 使用场景4.3 示例代码 五、views::zip 与 views::zip_transform 的对比5.1 功能差异5.2…...

Starrocks的主键表涉及到的MOR Delete+Insert更新策略

背景 写这个文章的作用主要是做一些总结和梳理&#xff0c;特别是正对大数据场景下的实时写入更新策略 COW 和 MOR 以及 DeleteInsert 的技术策略的演进&#xff0c; 这也适用于其他大数据的计算存储系统。该文章主要参考了Primary Key table. 分析总结 Starrocks 的主键表主…...

【计算机视觉】OpenCV实战项目:基于OpenCV的车牌识别系统深度解析

基于OpenCV的车牌识别系统深度解析 1. 项目概述2. 技术原理与算法设计2.1 图像预处理1) 自适应光照补偿2) 边缘增强 2.2 车牌定位1) 颜色空间筛选2) 形态学操作3) 轮廓分析 2.3 字符分割1) 投影分析2) 连通域筛选 2.4 字符识别 3. 实战部署指南3.1 环境配置3.2 项目代码解析 4.…...

20250513_问题:由于全局Pytorch导致的错误

文章目录 前言问题&#xff1a;由于全局Pytorch导致的错误找到问题(1)找到问题(2) 总结 前言 问题&#xff1a;由于全局Pytorch导致的错误 代码报错显示无法使用CUDA AttributeError: module ‘torch._C’ has no attribute ‘_cuda_setDevice’ 找到问题(1) import torch pri…...

flinksql实践(从kafka读数据)

本案例是基于flinksql实现的&#xff0c;将逐步实现从kafka读写数据&#xff0c;聚合查询&#xff0c;关联维表(外部系统)等。 环境准备 首先确保电脑已经安装好zookeeper、kafka、flink。本文flink使用单机模式&#xff0c;zookeeper和kafka也使用单机配置。(环境配置部分可以…...

Linux系统:文件系统前言,详解CHSLBA地址

本节重点 理解硬盘的组成结构与工作原理理解柱面、扇区CHS地址进行寻址对整块硬盘的逻辑抽象LBA地址进行寻址LBA与CHS地址的相互转换 一、初识硬盘 1.1 基本概念 硬盘&#xff08;Hard Disk Drive&#xff0c;HDD&#xff09;是一种用于存储和检索数据的计算机硬件设备。它…...

2025年01月10日浙江鑫越系统科技前端面试

目录 vue2 和 vue3 的区别vue 怎么封装组件js 怎么把一个数组置空怎么组件自己调用自己的组件v-bind:attribute 和 v-bind“{attribute}” 的区别var let const 的区别this 指向作用域链闭包原型链事件循环 1. vue2 和 vue3 的区别 Vue 2 和 Vue 3 在多个方面存在区别&#…...

2025.05.11阿里云机考真题算法岗-第三题

📌 点击直达笔试专栏 👉《大厂笔试突围》 💻 春秋招笔试突围在线OJ 👉 笔试突围OJ 03. 镜像追踪游戏 问题描述 A先生正在玩一款名为「镜像追踪」的游戏。游戏在一个 n n n...

实景三维建模软件应用场景(众趣科技实景三维建模)

实景三维建模软件应用场景概述 实景三维建模软件&#xff0c;作为数字化时代的重要工具&#xff0c;不仅能够真实、立体、时序化地反映和表达物理世界&#xff0c;还为国家的基础设施建设和数字化发展提供了有力的支撑。 在测绘与地理信息领域&#xff0c;实景三维建模软件是构…...

centos中libc.so.6No such file的解决方式

你在运行安装程序时遇到了以下错误&#xff1a; Configuring the installer for this systems environment...strings: /lib/libc.so.6: No such file 这个错误通常是由于系统中缺少 glibc&#xff08;GNU C Library&#xff09;或其相关文件导致的。glibc 是 Linux 系统中的…...

MapReduce打包运行

1. 编写 MapReduce 程序 首先需要编写 MapReduce 程序&#xff0c;通常包含 Mapper、Reducer 和 Driver 类。例如&#xff0c;一个简单的 WordCount 程序&#xff1a; java import java.io.IOException; import java.util.StringTokenizer;import org.apache.hadoop.conf.Con…...

RustDesk:开源电脑远程控制软件

RustDesk&#xff1a;开源电脑远程控制软件 RustDesk&#xff1a;开源电脑远程控制软件一、RustDesk 简介二、下载教程2.1 桌面版下载2.2 Android 版下载 三、安装教程3.1 桌面版安装 四、功能讲解4.1 远程控制4.2 文件传输4.3 安全可靠4.4 自定义服务器 五、RustDesk技术架构解…...

【Unity】WebGL开发问题汇总

1 前言 主要记录下WebGL开发过程中遇到的各种问题。 2 问题 2.1 中文字体不显示 问题&#xff1a; 经典问题了。将项目打包在WebGL平台后&#xff0c;运行发现所用中文字体都不现实了。 解决办法&#xff1a; 替换Text组件的“字体”。可以将电脑字体复制到项目当中然后替换组…...

华为海思系列----昇腾张量编译器(ATC)模型转换工具----入门级使用指南(LINUX版)

由于官方SDK比较冗余且经常跨文档讲解且SDK整理的乱七八糟,对于新手来说全部看完上手成本较高,本文旨在以简短的方式介绍 CAFFE / ONNX 模型转 om 模型,并进行推理的全流程。希望能够帮助到第一次接触华为海思框架的道友们。大佬们就没必要看这种基础文章啦! 注:本…...

c++STL-list的模拟实现

cSTL-list的模拟实现 list源码剖析list模拟实现list构造函数拷贝构造函数赋值重载迭代器 iterator访问结点数size和判空尾插 push_back头插 push_front尾删pop_back头删pop_front插入 insert删除 erase清空clear和析构函数访问结点 参考程序 list源码剖析 建议先看cSTL-list的…...

RabbitMQ 核心概念与消息模型深度解析(二)

四、代码实战 了解了 RabbitMQ 的核心概念和消息模型后&#xff0c;接下来我们通过代码实战来进一步加深对它们的理解和掌握。下面将以 Java 和 Spring AMQP 为例&#xff0c;展示如何使用 RabbitMQ 进行消息的发送和接收。 4.1 环境准备 在开始编写代码之前&#xff0c;需要…...

JAVA研发+前后端分离,ZKmall开源商城B2C商城如何保障系统性能?

在电商行业竞争白热化的当下&#xff0c;B2C 商城系统的性能表现成为决定用户留存与商业成败的关键因素。ZKmall 开源商城凭借 Java 研发与前后端分离架构的深度融合&#xff0c;构建起一套高效、稳定且具备强大扩展性的系统架构&#xff0c;从底层技术到上层应用全方位保障性能…...

【android bluetooth 框架分析 02】【Module详解 6】【StorageModule 模块介绍】

1. 背景 我们在 gd_shim_module 介绍章节中&#xff0c;看到 我们将 StorageModule 模块加入到了 modules 中。 // system/main/shim/stack.cc modules.add<storage::StorageModule>();在 ModuleRegistry::Start 函数中我们对 加入的所有 module 挨个初始化。 而在该函…...

Datawhale 5月llm-universe 第1次笔记

课程地址&#xff1a;GitHub - datawhalechina/llm-universe: 本项目是一个面向小白开发者的大模型应用开发教程&#xff0c;在线阅读地址&#xff1a;https://datawhalechina.github.io/llm-universe/ 难点&#xff1a;配置conda环境变量 我用的vscode github方法 目录 重要…...

Linux架构篇、第五章git2.49.0部署与使用

Linux_架构篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;git2.49.0部署与使用 版本号: 1.0,0 作者: 老王要学习 日期: 2025.05.13 适用环境: Centos7 文档说明 这份文档聚焦于在 CentOS 7 环境下部署和…...

南方科技大学Science! 自由基不对称催化新突破 | 乐研试剂

近日&#xff0c;南方科技大学刘心元教授团队联合浙江大学洪鑫教授团队在自由基不对称催化领域取得新进展。课题组开发了一系列大位阻阴离子 N,N,P-配体&#xff0c;用于铜催化未活化外消旋仲烷基碘与亚砜亚胺的不对称胺化反应。该反应表现出广泛的底物兼容性&#xff0c;涵盖具…...

手机换IP真的有用吗?可以干什么?

在当今数字化时代&#xff0c;网络安全和个人隐私保护日益受到重视。手机作为我们日常生活中不可或缺的工具&#xff0c;其网络活动痕迹往往通过IP地址被记录和追踪。那么&#xff0c;手机换IP真的有用吗&#xff1f;它能为我们带来哪些实际好处&#xff1f;本文将为你一一解答…...

【C++详解】类和对象(上)类的定义、实例化、this指针

文章目录 一、类的定义1、类定义格式2、访问限定符3、类域 二、实例化1、实例化概念2、对象大小 三、this指针 一、类的定义 1、类定义格式 class为定义类的关键字&#xff0c;Stack为类的名字&#xff0c;{}中为类的主体&#xff0c;注意类定义结束时后面分号不能省略。类体中…...

C语言—再学习(数据的存储类别)

在c语言中&#xff0c;每个变量和函数都有两个属性&#xff1a;数据类型和数据的存储类别 C的存储类别包括4种&#xff1a;自动挡&#xff08;auto&#xff09;、静态的&#xff08;static&#xff09;、寄存器的&#xff08;register&#xff09;、外部的&#xff08;extern&…...

软考软件评测师——计算机组成与体系结构(分级存储架构)

一、虚拟存储技术 虚拟存储系统通过软硬件协同实现内存扩展&#xff0c;其核心特征包括&#xff1a; 逻辑容量扩展能力&#xff1a;实际物理内存与外存结合&#xff0c;呈现远大于物理内存的连续地址空间动态加载机制&#xff1a;程序运行时仅加载必要部分到内存&#xff0c;…...

需求跟踪矩阵准确性的5大策略

需求跟踪矩阵的准确性可显著提升软件项目质量&#xff0c;确保需求的全面覆盖、减少遗漏和偏差&#xff0c;有利于优化变更管理&#xff0c;降低返工风险&#xff0c;最终保障产品符合用户预期和业务目标。如果不能保证跟踪矩阵的准确性&#xff0c;可能会导致需求遗漏、测试覆…...

【调度算法】MAPF多智能体路径规划问题

参考链接&#xff1a;https://blog.csdn.net/qq_43353179/article/details/129396325 在这篇博客的基础上对一些省略的部分进行补充。 网站&#xff1a;https://mapf.info/ 可行性判断 1. k-鲁棒性&#xff08;k-robust MAPF&#xff09; 在经典 MAPF 中&#xff0c;只要所有…...

迅龙3号基于兆讯MH22D3适配CST328多点触摸驱动开发笔记

MH22D3芯片是兆讯公司新推出的基于cortex-M3内核的新一代芯片&#xff0c;专注于显示应用&#xff0c;其主频高达216Mhz&#xff0c;64KB SRAM&#xff0c;512KB Flash&#xff0c;开发UI应用游刃有余。详细介绍请看&#xff1a;MH22D3新一代显控应用性价比之王 新龙微基于MH22…...