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

leetcode 169.Majority Element

news 来源：原创 2025/7/1 10:58:06

这道题虽然简单，但适合用来练习各种解法。《剑指offer》5.2节面试题29与此题一样，并且给出了leetcode官方题解未给出的快速选择的解法。

方法一、用哈希表解决

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int> count;int majority = 0;int cnt = 0;for(auto num:nums){count[num]++;if(count[num] > cnt){cnt = count[num];majority = num;}}return majority;}
};

方法二、先排序再取nums[n/2]

class Solution {
public:int majorityElement(vector<int>& nums) {int len = nums.size();srand(time(0));quick_sort(nums,0,len-1);return nums[len/2];}int partition(vector<int>& nums,int left,int right){if(left >= right)return left;int random = rand()%(right - left +1);swap(nums[left],nums[left + random]);int pivot = nums[left];while(left < right){while(left<right && pivot < nums[right]) right--;nums[left] = nums[right];  while(left<right && nums[left]<=pivot) left++;nums[right] = nums[left];}nums[left] = pivot;return left;}void quick_sort(vector<int>& nums,int left,int right){if(left>=right) return;int pivot_pos = partition(nums,left,right);quick_sort(nums,left,pivot_pos-1);quick_sort(nums,pivot_pos+1,right);}
};

方法三、快速选择

由于方法二可知，问题等价于求数组排好序后的第n/2个元素。那么由快速排序算法的思想，其实不用把整个数组排序结束，就可以找到排好序后的第n/2个元素，也就是快速选择算法。

这种解法，leetcode官方没有给出。

class Solution {
public:int majorityElement(vector<int>& nums) {srand(time(0));return quick_select(nums,0,nums.size()-1,nums.size()/2);}int partition(vector<int>& nums,int left,int right){if(left >= right) return left;int random_pos = left + rand()%(right - left +1);swap(nums[left],nums[random_pos]);int pivot = nums[left];while(left<right){while(left<right && pivot <= nums[right]) right--;nums[left] = nums[right];while(left<right && nums[left] < pivot) left++;nums[right] = nums[left];}nums[left] = pivot;return left;}int quick_select(vector<int>& nums,int left,int right,int k){if(left>=right) return nums[left];int pivot_pos = partition(nums,left,right);if(pivot_pos == k)return nums[pivot_pos];else if(pivot_pos > k)return quick_select(nums,left,pivot_pos-1,k);elsereturn quick_select(nums,pivot_pos+1,right,k);}
};

方法四、随机化方法

class Solution {
public:int majorityElement(vector<int>& nums) {srand(0);int len = nums.size();int random = 0; int cnt = 0;while(true){random = rand()%len;cnt = 0;for(auto num:nums){if(num == nums[random]){cnt++;if(cnt >len/2)return num;}}}}
};

方法五、分治法

class Solution {
public:int majorityElement(vector<int>& nums) {return divide_conquer(nums,0,nums.size()-1);}int divide_conquer(vector<int>& nums,int left,int right){if(left>=right)return nums[left];int mid = left + (right - left)/2;int majorityLeft = divide_conquer(nums,left,mid);int majorityRight = divide_conquer(nums,mid+1,right);if(majorityLeft == majorityRight)return majorityLeft;int cnt = 0;for(int i = left;i <= right;i++){if(nums[i] == majorityLeft){cnt++;if(cnt > (right - left +1)/2)return majorityLeft;}}return majorityRight;}
};

方法六、Boyer-Moore投票法

《剑指offer》5.2节也给出了这种解法

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

leetcode 169.Majority Element

这道题虽然简单，但适合用来练习各种解法。《剑指offer》5.2节面试题29与此题一样，并且给出了leetcode官方题解未给出的快速选择的解法。方法一、用哈希表解决 class Solution { public:int majorityElement(vector<int>& nums) {unordered…...

编程日记 2025/7/1 10:58:06

魔改chromium——基础环境搭建

谷歌chromium环境要求详细文档软件和环境要求，必须安装，硬性要求系统环境：Windows 10，内存最小8GB，推荐16GB，NTFS格式磁盘最少100GB空间Git版本：安装最新版本即可，Git桌面端下载…...

编程日记 2025/7/1 10:55:20

[网络_1] 因特网 | 三种交换 | 拥塞 | 差错 | 流量控制

目录一、网络、互连网与因特网二、因特网发展三、因特网的组成与功能四、计算机网络的分类五、因特网的标准化与意义一、三种传输方式：电路交换 vs 报文交换 vs 分组交换 1. 电路交换（Circuit Switching）——像“打电话” 2. 报…...

编程日记 2025/7/1 10:41:10

android 何如查找内网设备 IP

前沿最近在与嵌入式设备打交道，需要对设备进行配网。发现 UpnP 服务不稳定，经常收不到设备的信息。就想着能不能通过内网查找到 IP 后，直接与设备通信，不停的请求设备信息。 1.Android 端通过 UDP 组播（Multicast）查找设备如果嵌入式设备支持 UDP 组播，Android 端可…...

编程日记 2025/7/1 10:49:27

Oracle数据库数据编程SQL＜3.5 PL/SQL 存储过程(Procedure)＞

存储过程(Stored Procedure)是 Oracle 数据库中一组预编译的 PL/SQL 语句集合，存储在数据库中并可通过名称调用执行。它们是企业级数据库应用开发的核心组件。目录一、存储过程基础 1. 存储过程特点 2. 创建基本语法 3. 存储过程优点 4. 简单示例二、没有…...

编程日记 2025/7/1 10:54:27

六级词汇量积累day13

commend 表扬 exhaust 耗尽，用尽 weary 疲惫的，劳累的 fatigue 疲惫，劳累 obese 臃肿的，肥胖的 adopt 采纳，收养 adapt 适应 accomplish 完成，实现 accomplishment 成就 achieve 实现，完成 achi…...

编程日记 2025/7/1 10:47:26

将所有1x1转化为2x2 即1x1的方块➗4 然后计算平方数记得-1 2 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter;public class Main{static BufferedReader in new BufferedReader(new In…...

编程日记 2025/7/1 10:53:14

OpenCV图像输入输出模块imgcodecs（imwrite函数的用法）

《OpenCV计算机视觉开发实践：基于Python（人工智能技术丛书）》(朱文伟，李建英)【摘要书评试读】- 京东图书 3.2.3 imwrite保存图片函数imwrite可以用来输出图像到文件，其声明如下： imwrite(filename,…...

编程日记 2025/7/1 0:23:27

win 远程 ubuntu 服务器安装图形界面

远程结果：无法使用docker环境使用此方法注意要写IP和:数字在 ubuntu 服务器上安装如下： # 安装 sudo apt-get install tightvncserver # 卸载 sudo apt purge tightvncserver sudo apt autoremove#安装缺失的字体包： sudo apt update s…...

编程日记 2025/7/1 10:54:26

地下管线三维建模软件工具MagicPipe3D V3.6.1

经纬管网建模系统MagicPipe3D，基于二维矢量管线管点数据本地离线参数化构建地下管网三维模型（包括管道、接头、附属设施等），输出标准3DTiles、Obj模型等格式，支持Cesium、Unreal、Unity、Osg等引擎加载进行三维可视化、…...

编程日记 2025/7/1 4:08:53

vue子组件生命周期的执行顺序

在 Vue 中，子组件的生命周期钩子函数的执行顺序受父组件的影响，通常遵循**“先创建子组件，后创建父组件；先销毁父组件，后销毁子组件”**的原则。 1. 组件创建（挂载）阶段当父组件挂载时&#x…...

编程日记 2025/7/1 10:08:21

【含文档+PPT+源码】基于微信小程序的在线考试与选课教学辅助系统

项目介绍本课程演示的是一款基于微信小程序的在线考试与选课教学辅助系统，主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。 1.包含：项目源码、项目文档、数据库脚本、软件工具等所有资料 2.带你从零开始部署运行本套系统…...

编程日记 2025/7/1 4:47:39

树莓派超全系列文档--(17)树莓派配置显示器

树莓派配置显示器显示支持 HDMI 显示器设置分辨率和旋转手动设置分辨率和旋转确定显示设备名称设置自定义分辨率设置自定义旋转控制台分辨率和旋转文章来源： http://raspberry.dns8844.cn/documentation 原文网址显示要配置 Raspberry Pi 使用非默认显示模式…...

编程日记 2025/7/1 10:16:12

python将pdf文件转为图片，如果pdf文件包含多页，将转化的多个图片通过垂直或者水平合并成一张图片

要将PDF文件转换为图片，并将多页PDF垂直合并成一张图片，可以使用PyMuPDF（也称为fitz）库来读取PDF文件，并使用Pillow库来处理和合并图片。以下是一个示例代码，展示了如何实现这个功能： 首先&…...

编程日记 2025/7/1 10:30:50

JVM基础原理

JVM是一个虚拟化的计算机，它可以执行Java字节码文件（.class文件），实现Java程序跨平台的特性。JVM负责将Java程序的字节码翻译成具体操作系统的机器码，从而能够在不同的平台上运行。JVM的核心原理涉及以下几个重要方面 …...

编程日记 2025/6/30 23:29:57

Miniforge3高效管理 Python环境：2025年最新实践指南

Miniforge3 高效管理 Python 环境：2025 年最新实践指南在现代开发中，灵活高效地管理 Python 环境至关重要。Miniforge3 作为一款轻量级 Conda 管理工具，不仅默认采用更新更快的 conda-forge 软件源，还对 ARM 架构（例如 Apple M1/M2/M3）有着出色的适配性。相比于传统的 …...

编程日记 2025/7/1 10:03:35

31天Python入门——第17天:初识面向对象

你好，我是安然无虞。文章目录面向对象编程1. 什么是面向对象2. 类(class)3. 类的实例关于self 4. 对象的初始化5. __str__6. 类之间的关系继承关系组合关系 7. 补充练习面向对象编程 1. 什么是面向对象面向对象编程是一种编程思想,它将现实世界的概念和关系映…...

编程日记 2025/7/1 10:04:24

困于环中的机器人

************* c topic: 1041. 困于环中的机器人 - 力扣（LeetCode） ************* Inspect the topic first. And it looks really familiar with another robot topic. 657. 机器人能否返回原点 - 力扣（LeetCode）https://lee…...

编程日记 2025/7/1 10:19:09

阿里 FunASR 开源中文语音识别大模型应用示例（准确率比faster-whisper高）

文章目录 Github官网简介模型安装非流式应用示例流式应用示例 Github https://github.com/modelscope/FunASR 官网 https://www.funasr.com/#/ 简介 FunASR是一个基础语音识别工具包，提供多种功能，包括语音识别（ASR）、语音端…...

编程日记 2025/7/1 10:38:12

spring boot前后端开发上传文件时报413(Request Entity Too Large)错误的可能原因及解决方案

可能原因及解决方案 1. Spring Boot默认文件大小限制原因：Spring Boot默认单文件最大为1MB，总请求体限制为10MB。解决方案： 在application.properties中配置：spring.servlet.multipart.max-file-size10MB # 单文件最大 spring…...

编程日记 2025/7/1 9:00:02

Transformer：破局山地暴雨预测的「地形诅咒」--AI智能体开发与大语言模型的本地化部署、优化技术

极端降雨预测的技术痛点与边缘破局 1. 传统预警系统的三重瓶颈‌ ‌延迟致命‌：WRF模式在1km分辨率下3小时预报耗时>45分钟，错过山洪黄金响应期 ‌地形干扰大‌：复杂地形区（如横断山脉）降水预测误差超50% ‌数据…...

编程日记 2025/7/1 8:54:29

游戏引擎学习第187天

看起来观众解决了上次的bug 昨天遇到了一个相对困难的bug，可以说它相当棘手。刚开始的时候，没有立刻想到什么合适的解决办法，所以今天得从头开始，逐步验证之前的假设，收集足够的信息，逐一排查可能的原因&a…...

编程日记 2025/6/28 4:34:14

05-02-自考数据结构（20331）- 动态查找-知识点

自考数据结构动态查找算法主要讲二叉树和平衡二叉树，但是感觉到了，就又续接了一部分，所以这篇备考的小伙伴着重看前两种就可以了。知识拓扑知识点介绍二叉排序树(BST) 定义二叉排序树(Binary Search Tree)又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二…...

编程日记 2025/6/28 1:23:14

PyQt6实例_批量下载pdf工具_使用pyinstaller与installForge打包成exe文件

目录前置： 步骤： step one 准备好已开发完毕的项目代码 step two 安装pyinstaller step three 执行pyinstaller pdfdownload.py，获取初始.spec文件 step four 修改.spec文件，将data文件夹加入到打包程序中 step five 增加…...

编程日记 2025/6/28 1:23:18

NVR接入录像回放平台EasyCVR视频融合平台城市/乡镇污水处理厂解决方案

一、方案背景随着经济的快速发展和城市化的加快，城市污水排放量急剧增加，给城市环境和粮食安全带来了威胁。因此，污水处理厂的建设和高效运营成为对城市环境保护的重要任务。目前，国内许多城市虽已建成污水处理系统&#xff0…...

编程日记 2025/6/28 1:30:36

Vue2 vs Vue3 生命周期全面对比：created 的进化与革新！！！

🎯 Vue2 vs Vue3 生命周期全面对比：created 的进化与革新 🔥 核心差异全景图一、钩子函数命名与定位变化 1. 命名规范革新 Vue2 钩子Vue3 钩子 (Options API)Vue3 Composition APIbeforeCreate❌ 无setup() 替代created✅ 保留setup() 替代…...

编程日记 2025/7/1 8:36:13

Ubuntu 22.04安装MongoDB：GLM4模型对话数据收集与微调教程

在Ubuntu 22.04安装MongoDB Community Edition的教程请点击下方链接进行参考： 点击这里获取MongoDB Community Edition安装教程今天将为大家带来如何微调GLM4模型并连接数据库进行对话的教程。快跟着小编一起试试吧~ 1. 大模型 ChatGLM4 微调步骤 1.1 从 github…...

编程日记 2025/6/28 4:01:42

并查集（Union-Find Set）课程笔记

目录 1. 并查集原理 2. 并查集的实现 3. 并查集应用应用 1：省份数量问题应用 2：等式方程的可满足性 1. 并查集原理并查集用于处理需要将不同元素划分成若干不相交集合的问题。最开始时，每个元素都是单独的一个集合，随后根…...

编程日记 2025/6/28 5:24:53

算法刷题记录——LeetCode篇(1.4) [第31~40题](持续更新)

更新时间：2025-03-29 算法题解目录汇总：算法刷题记录——题解目录汇总技术博客总目录：计算机技术系列博客——目录页优先整理热门100及面试150，不定期持续更新，欢迎关注！ 32. 最长有效括号给你一个只包…...

编程日记 2025/6/30 20:02:08

【区块链安全 | 第十四篇】类型之值类型（一）

文章目录值类型布尔值整数运算符取模运算指数运算定点数地址（Address）类型转换地址成员balance 和 transfersendcall，delegatecall 和 staticcallcode 和 codehash 合约类型（Contract Types）固定大小字节数组&#x…...

编程日记 2025/6/28 1:23:25

一款超级好用且开源免费的数据可视化工具——Superset

认识Superset 数字经济、数字化转型、大数据等等依旧是如今火热的领域，数据工作有一个重要的环节就是数据可视化。看得见的数据才更有价值！ 现如今依旧有多数企业号称有多少多少数据，然而如果这些数据只是呆在冷冰冰的数据库或文件内则毫无…...

编程日记 2025/6/28 1:23:47

android gradle一直编译不下来，可能是打开了gradle离线模式

gradle离线模式当然，如果本地已经将gradle，lib都下载下来了，也可以打开这个离线模式，不然重启AS的时候可能会重新走一次下载流程...

编程日记 2025/6/28 1:23:26

（C语言）学生信息表（学生管理系统）（基于通讯录改版）（正式版）（C语言项目）

1.首先是头文件： //student.h //头文件//防止头文件被重复包含#pragma once//宏定义符号常量，方便维护和修改 #define ID_MAX 20 #define NAME_MAX 20 #define AGE_MAX 5 #define SEX_MAX 5 #define CLA_MAX 20 //定义初始最大容量 #define MAX 1//定义结…...

编程日记 2025/6/28 1:27:41

【Linux】Linux 系统启动流程详解

1. BIOS/UEFI 阶段硬件自检（POST） BIOS/UEFI 执行硬件检查（内存、CPU、外设等）。若硬件异常，通过蜂鸣码或屏幕提示错误。选择启动设备按配置顺序（硬盘、U盘、网络等）寻找可引导设备。BIOS&a…...

编程日记 2025/6/28 1:27:31

Jetson 设备卸载 OpenCV 4.5.4 并编译安装 OpenCV 4.2.0

‌一、卸载 OpenCV 4.5.4‌ 清除已安装的 OpenCV 库‌ sudo apt-get purge libopencv* python3-opencv # 卸载所有APT安装的OpenCV包‌:ml-citation{ref"1,3" data"citationList"}sudo apt autoremove # 清理残留依赖‌:ml-citation{ref"1,4"…...

编程日记 2025/6/28 6:29:56

【计算机网络】OSI七层模型完全指南：从比特流到应用交互的逐层拆解

OSI模型导读一、概念二、模型层次结构2.1 物理层（Physical Layer）2.2 数据链路层（Data Link Layer）2.3 网络层（Network Layer）2.4 传输层（Transport Layer）2.5 会话层&…...

编程日记 2025/6/27 21:24:54

渗透测试：登录页面的测试-弱口令思路和实战

渗透测试：登录页面的测试思路和实战渗透测试（Penetration Testing），也称为“渗透性测试”，是一种评估计算机系统、网络或Web应用安全性的一种方法。它通过模拟真实世界中的攻击手段和策略，来检测目标系统…...

编程日记 2025/6/28 3:45:27

Android BottomNavigationView 完全自定义指南：图标、文字颜色与选中状态

1. 核心功能概述通过 Material Design 的 BottomNavigationView，你可以轻松实现以下自定义： ✅ 动态切换选中/默认图标 ✅ 自定义选中与默认文字颜色 ✅ 控制文字显示模式（始终显示/仅选中显示/自动隐藏） ✅ 添加动画和高级样…...

编程日记 2025/6/28 1:23:24

提示词工程

参考网站：提示工程指南 – Nextra 声明：我现在也才刚刚开始学习人工智能，我会着重于 agent 的学习，如果有不对的地方请大家及时指出。模型设置前言在向大模型发送请求时，常常能看到以下参数： {&qu…...

编程日记 2025/6/28 4:08:59

分页查询原理与优化方案完全指南

分页查询原理与优化方案完全指南一、分页查询基础原理 1.1 传统分页实现方式分页查询的核心目的是将大数据集分割成多个小块进行展示，最常见的实现方式是使用LIMIT-OFFSET语法： -- 基础分页查询 SELECT * FROM table_name ORDER BY id LIMIT page_size OFFSET (page_n…...

编程日记 2025/6/29 9:53:23

嵌入式软件设计规范框架（MISRA-C 2012增强版）

以下是一份基于MISRA-C的嵌入式软件设计规范（完整技术文档框架），包含编码规范、安全设计原则和工程实践要求： 嵌入式软件设计规范（MISRA-C 2012增强版） 一、编码基础规范 1.1 文件组织头文件保护 /* 示…...

编程日记 2025/6/28 1:27:51

课程6. 决策树

课程6. 决策树决策树直觉模型结构几何解释决策树的构建ID3算法信息内容标准使用决策树处理差距推广到回归问题分支标准与经典损失函数的关系过度拟合和欠拟合欠拟合过拟合优点和缺点案例随机生成数据集分类IRIS 数据集解决回归问题的一个简短例子决策树今天我们继续探索一…...

编程日记 2025/6/28 1:23:30

【UE5.3.2】初学1：适合初学者的入门路线图和建议

3D人物的动作制作大神分析：3D人物的动作制作通常可以分为以下几个步骤：角色绑定（Rigging）：将3D人物模型绑定到一个骨骼结构上，使得模型能够进行动画控制。动画制作（Animation）：通过控制骨骼结构，制作出人物的各种动作，例如走路、跳跃、打斗等。动画编辑（Ani…...

编程日记 2025/6/30 20:35:27

OpenCV 图形API（4）内核 API

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述 G-API 背后的核心理念是可移植性——使用 G-API 构建的流水线必须是可移植的（或者至少具备可移植的能力）。这意味着&…...

编程日记 2025/6/30 20:15:11

pom.xml与.yml，java配置参数传递

pom.xml与 .yml java配置参数传递在Java项目中，通过 pom.xml 和 .yml 文件（如 application.yml）传递变量通常涉及构建时（Maven）和运行时（Spring Boot）两个阶段的配置。以下是具体的实现方法&…...

编程日记 2025/6/28 4:23:46

LeetCode算法题(Go语言实现)_21

题目给你一个整数数组 arr，如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。一、代码实现 func uniqueOccurrences(arr []int) bool {freq : make(map[int]int)// 统计每个数字的出现次数for _, num : range arr {freq[n…...

编程日记 2025/6/30 5:00:35

Docker部署前后端分离项目

镜像下载在有网络的电脑下载镜像（Windows）：依次在CMD命令台执行以下代码 docker pull node:20docker pull openjdk:22-jdkdocker pull mysql:8.0docker pull nginx:1.27 删除镜像代码： docker rmi node:latest 查看镜像列表…...

编程日记 2025/6/28 1:57:53

Linux系统安装MySQL 8.0完整指南（新手友好版）

MySQL作为最流行的开源关系型数据库之一，广泛应用于各种开发和生产环境。本教程将详细介绍在Linux系统上安装MySQL 8.0的全过程，包括卸载旧版本、安装新版本、基础配置和远程连接设置，特别适合Linux新手学习使用。一、卸载旧版MySQL&#x…...

编程日记 2025/6/28 1:23:44

第二次作业

#创建表，把id设为主键 mysql> create table test02(-> id int primary key, #----主键约束-> name varchar(50)-> ); Query OK, 0 rows affected (0.02 sec) #插入数据测试 mysql> insert into test02 values(1,"成都"); Query OK, 1 r…...

编程日记 2025/6/27 8:31:34

AI大模型下传统 Spring Java工程开发的演进和变化方向

1. 背景和动因传统Spring开发优势：Spring生态以稳定、模块化、依赖注入（DI）等特性著称，长期支撑企业级应用开发，具备高扩展性和可维护性。AI大模型崛起：近几年，LLM（如GPT-4、LLaMA…...

编程日记 2025/6/28 2:21:51