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

169. 多数元素

题目

给定一个大小为 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 * 10^4
  • -10^9 <= nums[i] <= 10^9

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

代码

完整代码

int majorityElement(int* nums, int numsSize) {int most = nums[0];int cnt = 1;for (int i = 1; i < numsSize; i++) {if (nums[i] == most) {cnt++;} else {cnt--;if (cnt < 0) {most = nums[i];cnt = 1;}}}return most;
}

思路分析

该问题的最优解法是使用Boyer-Moore多数投票算法,时间复杂度为 O(n),空间复杂度为 O(1)。这个算法的核心思想是维护一个候选多数元素以及其计数器。当遍历数组时,如果当前元素与候选多数元素相同,计数器加一;如果不同,计数器减一。当计数器减为零时,将当前元素设为候选多数元素,并重置计数器为一。最终剩下的候选多数元素即为数组中的多数元素。

拆解分析

初始化候选元素和计数器

初始化候选多数元素 most 为数组的第一个元素,计数器 cnt 为 1。

int most = nums[0];
int cnt = 1;

遍历数组更新候选元素和计数器

遍历数组,从第二个元素开始:

  • 如果当前元素等于候选多数元素,计数器加一;
  • 否则,计数器减一;
  • 如果计数器减为零,更新候选多数元素为当前元素,并重置计数器为一。
for (int i = 1; i < numsSize; i++) {if (nums[i] == most) {cnt++;} else {cnt--;if (cnt < 0) {most = nums[i];cnt = 1;}}
}

返回候选多数元素

最终返回候选多数元素 most

return most;

复杂度分析

  • 时间复杂度:O(n),其中 n 是数组的长度。我们只需遍历数组一次。
  • 空间复杂度:O(1),我们只使用了常数级别的额外空间。

结果

结果

一题多解

排序法

排序法思路分析

排序数组后,多数元素必定会出现在中间位置。我们可以直接返回排序后的数组中位于 n/2 位置的元素。

排序法复杂度分析

  • 时间复杂度:O(n log n),这是qsort的时间复杂度。
  • 空间复杂度:O(1),如果排序算法是原地排序,否则为 O(n)。

完整代码

#include <stdio.h>
#include <stdlib.h>int cmp(const void* a, const void* b) {return (*(int*)a - *(int*)b);
}int majorityElement(int* nums, int numsSize) {qsort(nums, numsSize, sizeof(int), cmp);return nums[numsSize / 2];
}

拆解分析

排序数组

使用标准库中的 qsort 函数对数组进行排序。

qsort(nums, numsSize, sizeof(int), cmp);
返回中间元素

由于多数元素必定会出现在中间位置,直接返回排序后数组中 numsSize / 2 位置的元素。

return nums[numsSize / 2];

结果

在这里插入图片描述

相关文章:

169. 多数元素

题目 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a;nums [3,2,3]输出&#xff1a;3 …...

ADS基础教程19 - 电磁仿真(EM)基本概念和实操

EM介绍 一、引言二、基本概念1.EM介绍2.Momentum介绍3.FEM介绍4.Substrate介绍 三、创建Layout并进行Momentum仿真1.创建Layout2.添加Microtrip&#xff08;微带线&#xff09;3.添加Substrate4.Momentum仿真 四、总结 一、引言 本章节开始介绍EM的基本概念、内容以及实现具体…...

LabVIEW RT环境中因字符串拼接导致的系统崩溃问题

在LabVIEW实时操作系统&#xff08;RT&#xff09;环境中运行的应用程序出现字符串拼接后死机的问题&#xff0c;通常涉及内存管理、内存泄漏或其他资源管理问题。以下是一些指导和步骤&#xff0c;帮助解决这个问题&#xff1a; 1. 内存泄漏检测 字符串拼接会在内存中创建新…...

深层网络:层数多真的更好吗?

深层网络&#xff1a;层数多真的更好吗&#xff1f; 在深度学习的世界里&#xff0c;"深度"始终是一个热门话题。随着技术的发展&#xff0c;我们有了越来越多的方法来构建更深的神经网络&#xff0c;这似乎暗示着“层数越多&#xff0c;效果越好”。然而&#xff0…...

【QT5】<知识点> QT常用知识(更新中)

目录 一、更改文本颜色和格式 二、QT容器类 三、字符串与整数、浮点数之间的转换 四、QString常用功能 五、SpinBox的属性介绍 六、滑动、滚动、进度条和表盘LCD 七、时间、日期、定时器 一、更改文本颜色和格式 动态设置字体粗体&#xff1a;QFont对象的setBold方法动态…...

如何将AndroidStudio和IDEA的包名改为分层级目录

新版UIAndroidStudio 1、点击项目目录右上角如图所示的三个点点。 2、然后依次取消Hide empty middle package &#xff0c;Flatten package的勾选 3、注意&#xff1a;一定要先取消hide的勾选&#xff0c;不然目录不会完全分级&#xff08;做错了可以反过来重新设置&#x…...

北交字节联合提出ClassDiffusion: 使用显式类别引导的一致性个性化生成。

在个性化生成领域, 微调可能会引起过拟合导致模型无法生成与提示词一致的结果。针对这个问题&#xff0c;北交&字节联合提出ClassDiffusion&#xff0c;来提升个性化生成的一致性。 通过两个重要观察及理论分析提出了新的观点:一致性的损失是个性化概念语义偏移导致的, 还…...

37、matlab矩阵运算

1、前言 矩阵运算是指对矩阵的各种操作和运算&#xff0c;包括矩阵加法、矩阵减法、矩阵乘法、矩阵转置、求逆矩阵等。以下是常见的矩阵运算&#xff1a; 矩阵加法&#xff1a;对应位置的元素相加&#xff0c;要求加数和被加数的维度相同。 A B | a11 b11 | | a12 b12 | | …...

用软件实现的硬件——虚拟机

通过软件实现CPU和内存等硬件所具有的功能&#xff0c;并在计算机中运行循环的计算机技术称为虚拟机。使用虚拟机&#xff0c;就可以在一台计算机中运行多个循环出来的计算机。 近几年的计算机&#xff0c;除了硬件具有较高的性能外&#xff0c;CPU的性能也有了提升。因此&…...

[Shell编程学习路线]--shell中重定向和管道符(详细介绍)

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f6e0;️Shell编程专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年6月12日10点50分 &#x1f004;️文章质量&#xff1a;93分 ——前言—— 在Shell编程中&#xff0c;重定向和管道符是两个…...

Linux命令详解(1)

在Linux操作系统中&#xff0c;命令行界面&#xff08;CLI&#xff09;是一个强大的工具&#xff0c;它允许用户通过键入命令来与系统交互。无论是系统管理员还是普通用户&#xff0c;掌握一些基本的Linux命令都是非常重要的。在本文中&#xff0c;我们将探讨一些常用的Linux命…...

网工内推 | 深信服、中软国际技术支持工程师,最高13k*13薪

01 深信服 &#x1f537;招聘岗位&#xff1a;远程技术支持工程师 &#x1f537;任职要求&#xff1a; 一、专业能力和行业经验&#xff1a; ①具备友商同岗位工作经验1.5年以上&#xff0c;具备良好的分析和判断能力&#xff0c;有独立问题处理思路&#xff0c;具备常见协…...

实现卡片的展开缩放动画

原理&#xff0c;外层包裹一个元素&#xff0c;子元素分别是展开和收起的元素&#xff0c;然后对展开的元素添加动画&#xff0c;动画内容是随时间变化&#xff0c;将卡片的transform&#xff1a;rotateX属性进行调整&#xff0c;因为改变的是子元素的旋转&#xff0c;父元素高…...

实验:贪心算法

实验二&#xff1a;贪心算法 【实验目的】 应用贪心算法求解活动安排问题。 【实验性质】 验证性实验。 【实验要求】 活动安排问题是可以用贪心算法有效求解的很好的例子。 问题&#xff1a;有n个活动的集合A{1,2,…,n}&#xff0c;其中每个活动都要求使用同一资源&…...

Python学习笔记12 -- 有关布尔值的详细说明

一、布尔表达式 最终值为true 或者false 二、常见形式&#xff1a; 1、常量&#xff1a;true false 2、比较运算&#xff1a; and &#xff01; 3、复合运算&#xff1a; and and or 4、其他 例&#xff1a;检测闰年&#xff1a; def specialYearMine(year):if (year%4 …...

SQL-窗口函数合集

目录 1.窗口函数简介2.窗口的定义3.相关题目示例3.1 PERCENT_RANK()2346 以百分比计算排名 3.2 FIRST_VALUE()/LAST_VALUE()/NTH_VALUE()2388 将表中的空值更改为前一个值 1.窗口函数简介 MySQL 开窗函数&#xff08;Window Functions&#xff09;是 MySQL 8.0 版本引入的一个…...

2024 全球软件研发技术大会官宣,50+专家共话软件智能新范式!

2024年的全球软件研发技术大会&#xff08;SDCon&#xff09;由CSDN和高端IT咨询与教育平台Boolan联合主办&#xff0c;将于7月4日至5日在北京威斯汀酒店举行。本次大会的主题为“大模型驱动软件智能化新范式”&#xff0c;旨在探讨大模型和开源技术的发展如何引领全球软件研发…...

opencv快速安装以及各种查看版本命令

安装opencv并查看其版本&#xff0c;直接通过一个可执行文件实现。 #!/bin/bashwget https://codeload.github.com/opencv/opencv/zip/3.4 -O opencv-3.4.zip && unzip opencv-3.4.zip && cd opencv-3.4 && \mkdir build && cd build &&a…...

免费学习通刷课(免费高分)Pro版

文章目录 概要整体架构流程小结 概要 关于上一版的免费高分的学习通刷课&#xff0c;有很多人觉得还得登录太复杂了&#xff0c;然后我又发现了个神脚本&#xff0c;操作简单&#xff0c;可以后台挂着&#xff0c;但是还是建议调整速度到2倍速&#xff0c;然后找到你该刷的课&…...

线性数据结构-队列

队列&#xff08;Queue&#xff09;是一种先进先出&#xff08;First In First Out, FIFO&#xff09;的数据结构&#xff0c;它按照元素进入的顺序来处理元素。队列的基本操作包括&#xff1a; enqueue&#xff1a;在队列的末尾添加一个元素。dequeue&#xff1a;移除队列的第…...

K8s原生ML编排进入“编译期优化”时代(SITS 2026首次披露:eBPF驱动的模型感知调度器Alpha版已交付头部5家云厂商)

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;AI原生Kubernetes编排&#xff1a;SITS 2026 K8s for ML工作负载 SITS 2026 引入了专为机器学习工作负载深度优化的 AI-native Kubernetes 编排层&#xff0c;突破传统 K8s 在资源弹性、异构设备调度与…...

【LeetCode 手撕算法】(二分查找)搜索插入位置、搜索二维矩阵、查找数组相同的所有位置、搜索旋转排序数组、旋转升序数组的最小值

复杂度为O(log n)且有序用二分查找35-搜索插入位置思路&#xff1a;二分查找&#xff0c;左右指针 求中间值注意&#xff1a;while的查询条件是>class Solution {public int searchInsert(int[] nums, int target) {int left0;int rightnums.length-1;while(left<right){…...

大核小核架构的演进:从DVFS到异构计算,应对先进制程挑战

1. 项目概述&#xff1a;大核小核架构的十字路口在移动计算和嵌入式领域&#xff0c;ARM的“大核小核”&#xff08;big.LITTLE&#xff09;架构在过去十年里几乎成了高性能低功耗的代名词。从智能手机到平板电脑&#xff0c;再到如今的物联网边缘设备&#xff0c;这套将高性能…...

windows系统安装wsl安装opencode教程

使用 AI 助手&#xff08;OpenCode&#xff09;在 WSL2 中高效安全工作教程 背景 在 AI 极大发展的现在&#xff0c;AI 可以帮助我们完成很多工作。那么怎么让 AI 帮我们高效、安全地工作呢&#xff1f;以下是教程。 同时&#xff0c;大模型在 Windows 里面直接执行脚本时错…...

CANN/asc-devkit矢量取倒数API

asc_rcp 【免费下载链接】asc-devkit 本项目是CANN 推出的昇腾AI处理器专用的算子程序开发语言&#xff0c;原生支持C和C标准规范&#xff0c;主要由类库和语言扩展层构成&#xff0c;提供多层级API&#xff0c;满足多维场景算子开发诉求。 项目地址: https://gitcode.com/ca…...

【2024独家首发】Red Cabbage印相参数矩阵表:17组实测--no stylize值×--sref权重×色域压缩阈值,精准复现植物染料氧化还原曲线

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Red Cabbage印相的化学机理与Midjourney参数映射原理 花青素的pH响应性与图像显影基础 红甘蓝&#xff08;Red Cabbage&#xff09;提取液富含花青素&#xff08;anthocyanin&#xff09;&#xff0c;…...

ReAct不是格式游戏!揭秘让LLM从“文本生成器”变身“决策引擎”的底层逻辑

文章指出&#xff0c;ReAct常被误解为高级Prompt工程&#xff0c;但核心是闭环执行架构。真正的ReAct强调“决策-执行-反馈”循环&#xff0c;而非固定的Thought/Action/Observation格式。工程代码定义流程&#xff0c;模型生成内容&#xff0c;实现真实工具调用与反馈闭环。文…...

从Simulink模型到C代码:Assignment模块的‘Index Mode’选Zero还是One?一个影响深远的决定

从Simulink模型到C代码&#xff1a;索引模式选择的工程实践指南 在嵌入式软件开发中&#xff0c;模型与代码的协同设计一直是提高开发效率的关键环节。当Simulink模型工程师将算法模型转换为C代码时&#xff0c;一个看似简单的参数配置——Assignment模块的"Index Mode&q…...

Dell G15散热终极解决方案:开源温度控制中心完全指南

Dell G15散热终极解决方案&#xff1a;开源温度控制中心完全指南 【免费下载链接】tcc-g15 Thermal Control Center for Dell G15 - open source alternative to AWCC 项目地址: https://gitcode.com/gh_mirrors/tc/tcc-g15 Dell G15笔记本用户是否经常遭遇游戏卡顿、性…...

军用270V电源系统设计与模块化解决方案

1. 军用270V电源系统的核心挑战在军用电子设备领域&#xff0c;270V直流电源系统已成为现代战机、舰载设备和地面作战系统的标准配置。作为一名在军工电源领域工作十余年的工程师&#xff0c;我深刻理解这类系统设计面临的独特挑战。军用环境对电源的要求远高于商业应用&#x…...