leetcode 面试经典 150 题:多数元素

链接多数元素
题序号169
题型数组
解法1. 排序法、2. Boyer-Moore投票算法
难度简单
熟练度✅✅✅✅✅

题目

  • 给定一个大小为 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 log n),其中 n 是数组的长度。这意味着对于大型数组,排序方法可能比 Boyer-Moore 投票算法慢,后者的时间复杂度为 O(n)。
  3. c++ 实现算法
//排序法
class Solution2 {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        return (nums[nums.size()/2]);
    }
};

Boyer-Moore投票算法

  1. Boyer-Moore投票:Boyer-Moore投票算法是一种用于在数组中找出出现次数超过一半的元素(即多数元素)的高效算法。这个算法由Robert S. Boyer和J Strother Moore于1981年提出。算法的核心思想是通过两次遍历数组的过程来找出多数元素。
  2. 核心要点:该题适合使用Boyer-Moore投票算法,即在一个序列中找出一个出现次数超过n/2的元素(如果存在的话)。
  3. 复杂度:时间复杂度 O(n), 空间复杂度 O(1)
  4. c++ 实现算法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = 0;
        for(int i = 0; i < nums.size(); i++){
            if(count == 0){
                candidate = nums[i];
            }

            count += (candidate == nums[i]) ? 1 : -1;
        }
        
        return candidate;
    }
};
  1. 推演
  • 假设我们有一个数组 nums = [3, 2, 3]:

  • 初始化:count = 0,candidate = 0。

  • 遍历 nums[0] = 3:
    count 为0,所以将 nums[0] 设为 candidate,即 candidate = 3,count = 1。

  • 遍历 nums[1] = 2:
    nums[1] 与 candidate 不同,count 减1,count = 0。

  • 遍历 nums[2] = 3:
    count 为0,所以将 nums[2] 设为 candidate,即 candidate = 3,count = 1。

  • 遍历结束后,candidate = 3,这是数组中的多数元素。

完整demo

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = 0;
        for(int i = 0; i < nums.size(); i++){
            if(count == 0){
                candidate = nums[i];
            }

            count += (candidate == nums[i]) ? 1 : -1;
        }
        
        return candidate;
    }
};

//排序法
class Solution2 {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        return (nums[nums.size()/2]);
    }
};



int  main(){

    vector <int> nums = {3, 2, 3};
    Solution2 solution;

    int element = solution.majorityElement(nums);

    cout << "major elemet: " << element << endl;

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/950199.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

主机A与主机B建立TCP连接的三次握手过程

&#xff08; 1 &#xff09;主机 A 的 TCP 向主机 B 发出连接请求 SYN 报文段&#xff08;第一次握手&#xff09;。&#xff08; 1 分&#xff09; &#xff08; 2 &#xff09;一旦包含 SYN 报文段的 IP 数据报到达主机 B &#xff0c; SYN 报文段被从数据报…

SpringCloud系列教程:微服务的未来(六)docker教程快速入门、常用命令

对于开发人员和运维工程师而言&#xff0c;掌握 Docker 的基本概念和常用命令是必不可少的。本篇文章将带你快速入门 Docker&#xff0c;并介绍一些最常用的命令&#xff0c;帮助你更高效地进行开发、测试和部署。 目录 前言 快速入门 docker安装 配置镜像加速 部署Mysql …

Express 加 sqlite3 写一个简单博客

例图&#xff1a; 搭建 命令&#xff1a; 前提已装好node.js 开始创建项目结构 npm init -y package.json:{"name": "ex01","version": "1.0.0","main": "index.js","scripts": {"test": &q…

C++:字符数组

一、字符数组介绍 数组的元素如果是字符类型&#xff0c;这种数组就是字符数组&#xff0c;字符数组可以是一维数组&#xff0c;可以是二维数组 &#xff08;多维数组&#xff09;。我们接下来主要讨论的是一维的字符数组。 char arr1[5]; //⼀维字符数组 char arr2[3][5];//⼆…

基于SpringBoot实现的保障性住房管理系统

&#x1f942;(❁◡❁)您的点赞&#x1f44d;➕评论&#x1f4dd;➕收藏⭐是作者创作的最大动力&#x1f91e; &#x1f496;&#x1f4d5;&#x1f389;&#x1f525; 支持我&#xff1a;点赞&#x1f44d;收藏⭐️留言&#x1f4dd;欢迎留言讨论 &#x1f525;&#x1f525;&…

分享3个国内使用正版GPT的网站【亲测有效!2025最新】

1. molica 传送入口&#xff1a;https://ai-to.cn/url/?umolica 2. 多帮AI 传送入口&#xff1a;https://aigc.openaicloud.cn?inVitecodeMYAAGGKXVK 3. 厉害猫 传送入口&#xff1a;https://ai-to.cn/url/?ulihaimao

LabVIEW瞬变电磁接收系统

利用LabVIEW软件与USB4432采集卡开发瞬变电磁接收系统。系统通过改进硬件配置与软件编程&#xff0c;解决了传统仪器在信噪比低和抗干扰能力差的问题&#xff0c;实现了高精度的数据采集和处理&#xff0c;特别适用于地质勘探等领域。 ​ 项目背景&#xff1a; 瞬变电磁法是探…

CM3/4启动流程

CM3/4启动流程 1. 启动模式2. 启动流程 1. 启动模式 复位方式有三种&#xff1a;上电复位&#xff0c;硬件复位和软件复位。 当产生复位&#xff0c;并且离开复位状态后&#xff0c;CM3/4 内核做的第一件事就是读取下列两个 32 位整数的值&#xff1a; 从地址 0x0000 0000 处取…

快手短剧播放器uniapp如何引入与对接?

uniApp前端微短剧项目开源分享 开源地址&#xff1a;git开源下载地址 文章目录 快手短剧播放器uniapp如何引入与对接&#xff1f;1.引入短剧播放器2.创建文件kscomponents组件3.local-stream.js文件说明4.用户行为事件4.local-stream.ksml文件参考如下 快手短剧播放器uniapp如何…

.NET AI 开发人员库 --AI Dev Gallery简单示例--问答机器人

资源及介绍接上篇 nuget引用以下组件 效果展示&#xff1a; 内存和cpu占有&#xff1a; 代码如下&#xff1a;路径换成自己的模型路径 模型请从上篇文尾下载 internal class Program{private static CancellationTokenSource? cts;private static IChatClient? model;privat…

如何构建多层决策树

构建一颗多层的决策树时&#xff0c;通过递归选择最佳划分特征&#xff08;依据 信息增益 或 基尼系数&#xff09;对数据集进行划分&#xff0c;直到满足停止条件&#xff08;例如叶节点纯度达到要求或树的深度限制&#xff09;。以下是基于 信息增益 和 基尼系数 的递推公式和…

VSCode 使用鼠标滚轮控制字体

一、 文件 | 首选项 | 设置 二、单击在 settings.json中编辑 "editor.mouseWheelZoom": true 注注注意&#xff1a;保存哦&#xff01;ctrlS 三、测试 按住ctrl鼠标滚轮&#xff0c;控制字体大小

十年后LabVIEW编程知识是否会过时?

在考虑LabVIEW编程知识在未来十年内的有效性时&#xff0c;我们可以从几个角度进行分析&#xff1a; ​ 1. 技术发展与软件更新 随着技术的快速发展&#xff0c;许多编程工具和平台不断更新和改进&#xff0c;LabVIEW也不例外。十年后&#xff0c;可能会有新的编程语言或平台…

注册中心如何选型?Eureka、Zookeeper、Nacos怎么选

这是小卷对分布式系统架构学习的第9篇文章&#xff0c;第8篇时只回答了注册中心的工作原理的内容&#xff0c;面试官的第二个问题还没回答&#xff0c;今天再来讲讲各个注册中心的原理&#xff0c;以及区别&#xff0c;最后如何进行选型 上一篇文章&#xff1a;如何设计一个注册…

C++ 复习总结记录三

C 复习总结记录三 主要内容 1、类的六个默认成员函数 2、构造函数 3、析构函数 4、拷贝构造函数 5、赋值运算符重载 6、const 成员函数 7、取地址及 const 取地址操作符重载 一 类的六个默认成员函数 如果一个类中什么成员都没有&#xff0c;简称为空类。空类中并不是…

【简博士统计学习方法】第1章:4. 模型的评估与选择

4. 模型的评估与选择 4.1 训练误差与测试误差 假如存在样本容量为 N N N的训练集&#xff0c;将训练集送入学习系统可以训练学习得到一个模型&#xff0c;我们将这么模型用决策函数的形式表达&#xff0c;也就是 y f ^ ( x ) y\hat{f}(x) yf^​(x)&#xff0c;关于模型的拟合…

计算机网络 (30)多协议标签交换MPLS

前言 多协议标签交换&#xff08;Multi-Protocol Label Switching&#xff0c;MPLS&#xff09;是一种在开放的通信网上利用标签引导数据高速、高效传输的新技术。 一、基本概念 MPLS是一种第三代网络架构技术&#xff0c;旨在提供高速、可靠的IP骨干网络交换。它通过将IP地址映…

【Java】JVM内存相关笔记

Java虚拟机在执行Java程序的过程中会把它所管理的内存划分为若干个不同的数据区域。这些区域有各自的用途&#xff0c;以及创建和销毁的时间&#xff0c;有的区域随着虚拟机进程的启动而一直存在&#xff0c;有些区域则是依赖用户线程的启动和结束而建立和销毁。 程序计数器&am…

鸿蒙 ArkUI实现地图找房效果

常用的地图找房功能&#xff0c;是在地图上添加区域、商圈、房源等一些自定义 marker&#xff0c;然后配上自己应用的一些筛选逻辑构成&#xff0c;在这里使用鸿蒙 ArkUI 简单实现下怎么添加区域/商圈、房源等 Marker. 1、开启地图服务 在华为开发者官网&#xff0c;注册应用&…

STM32-WWDG/IWDG看门狗

WWDG/IWDG一旦开启不能关闭&#xff0c;可通过选项字节在上电时启动硬件看门狗&#xff0c;看门狗计数只能写入不能读取。看门狗启用时&#xff0c;T6bit必须置1&#xff0c;防止立即重置。 一、原理 独立看门狗-超时复位 窗口看门狗-喂狗&#xff08;重置计数器&#xff0c;…