leetcode做题笔记169. 多数元素
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:nums = [3,2,3] 输出:3
示例 2:
输入:nums = [2,2,1,1,1,2,2] 输出:2
思路一:排序后记录数的个数
c语言解法
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);int n = 1;for(int i = 0;i<numsSize-1;i++){if(nums[i]==nums[i+1]){n++;if(n*2>=numsSize)return nums[i];}else n=1;}return nums[0];}
分析:
本题要找出数组中相同元素个数大于数组长度一半的元素,可以先将原数组中数先排序一遍,利用循环记录前后相等的元素,当计数超过数组长度一半则返回该元素,否则返回数组第一个元素
优化:
因为要找到的数排序后一定为中位数,直接返回中位数即可
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];}
进阶思路:投票法
class Solution {
public:int majorityElement(vector<int>& nums) {int cnt = 0;int candidate = 0;for(const auto& t:nums){if(!cnt)candidate = t;cnt += candidate == t ? 1 : -1;}return candidate;}
};
分析:
运用投票法,投票法核心思路即若其他人投不同的票则直接抵消原来的一张票,最后剩下的则为所找元素
总结:
本题考察对数组循环计数的应用,记录相同元素,当记录数超过数组长度一半则返回,时间复杂度为O(nlogn),若使用投票法则可使时间复杂度为O(n)
相关文章:
leetcode做题笔记169. 多数元素
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入:nums [3,2,3] 输出:3 示例 …...
FATFS f_printf 如何支持写入浮点数据。
参考原子和网上的移植最新的fatfs系统后,挂载打开文件始终返回13错误代码,在自己的项目中移植最新的fatfs0.15版本解决问题,使用f_printf能成功进行浮点数据写入了 参考的文章如下: https://zhuanlan.zhihu.com/p/444427537 问题描述 在使用fatfs的f_printf向文件.csv中写入…...
postman忘记密码提交没响应
现象:通过客户端进到账户页面一直无响应,可copy the url 到浏览器进入页面,使用浏览器提交几次还是没响应。 实测有用方法: 1、通过手机进入官网 https://www.getpostman.com ,找到忘记密码入口。 2、多提交几次后&…...
初学vue,想自己找个中长期小型项目练练手,应该做什么?
前言 可以试着做一两个完整的后台管理项目后再去做其他的,下面推荐一些github上的vue后台管理的项目,可以自己选择性的练一下手 Vue2 1、iview-admin Star: 16.4k 基于 iview组件库开发的一款后台管理系统框架,提供了一系列的强大组件和基…...
【牛客面试必刷TOP101】Day11.BM63 跳台阶和 BM67 不同路径的数目(一)
作者简介:大家好,我是未央; 博客首页:未央.303 系列专栏:牛客面试必刷TOP101 每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!!!&…...
[NOIP 2022] 建造军营 题解
题目 P1 边双缩点 观察样例二,可以发现边双内的边可选可不选。由此考虑边双缩点,Tarjan 找桥即可,缩点后变成一棵树。 P2 设计状态 用最终合法答案形态截这颗树,设计 f u f_u fu 表示 u u u 子树内非空,且子树…...
射频识别技术(RFID)在智能制造模具管理中的应用
背景介绍 模具是工业生产的核心装备,被誉为“工业之母”,广泛应用于机械、汽车、轻工、电子、化工、冶金、建材等各个行业,是制造加工企业的重要资产,然而,传统的人工纸质记录方式已无法满足模具管理的需求࿰…...
奖品定制经营商城小程序的作用是什么
奖品是激励人员团体很好的方式,也是荣誉象征,奖牌、奖杯、高端礼盒等,同时市场中团体非常多,其需求也是很多,尤其定制方面,就更是不用说。 对奖品定制企业来说,除了线下门店获客经营外…...
深度学习常用脚本总结
👨💻个人简介: 深度学习图像领域工作者 🎉工作总结链接:https://blog.csdn.net/qq_28949847/article/details/128552785 链接中主要是个人工作的总结,每个链接都是一些常用demo,…...
hive数据表创建
目录 分隔符 分区表 二级分区 分桶表 外部表 分隔符 CREATE TABLE emp( userid bigint, emp_name array<string>, emp_date map<string,date>, other_info struct<deptname:string, gender:string>) ROW FORMAT DELIMITED FIELDS TERMINATED BY \t COL…...
查看本机Arp缓存,以及清除arp缓存
查看Arp缓存目录 Windows 系统使用 winR,输入cmd 在命令窗口输入 arp -a 删除Arp缓存目录 在命令窗口输入 arp -d * 查看主机路由表...
Unity MRTK Hololens2眼动交互
/** ** UnityVersion : 2021.3.6f1* Description : 眼部交互基类* Author: * CreateTime : 2023-10-11 09:43:20* Version : V1.0.0* * */using System.Collections.Generic; using Microsoft.MixedReality.Toolkit.Input; using UnityEngine;namespace MRTKExtend.EyeTrackin…...
接口自动化测试 —— 协议、请求流程
一、架构 CRM客户关系管理系统 SAAS Software As A Service 软件即服务 PAAS Platform AS A Service 平台即服务 快速交付→ 快:自己去干、有结果、事事有回音、持续改进 单体架构——》垂直架构——》面向服务架构——》微服务架构(分布式…...
JDK安装详细教程
JDK安装详细教程 国内大多数使用的是1.8的版本,对于初学者来说这个版本很友善,不过由于我安装过了1.8,所以我这里演示JDK21 的安装,过程并无区别,只在下载时注意选择1.8版本。1.8就是JDK8. 文章目录 JDK安装详细教程一…...
vulnhub_Fowsniff靶机渗透测试
Fowsniff靶机 靶机地址:https://www.vulnhub.com/entry/fowsniff-1,262/ 文章目录 Fowsniff靶机信息收集web渗透密码碰撞POP3邮件服务器渗透获取权限权限提升靶机总结 信息收集 通过nmap扫描,靶机开放22 80 110 143端口,110是pop3邮件服务…...
FPGA面试题(3)
一.FPGA和CPLD区别 FPGA:现场可编程门阵列CPLD:复杂可编程逻辑器件 二.多位异步信号如何同步 单比特异步信号 慢时钟域->快时钟域:同步打拍快时钟域->慢时钟域:先拓展位宽再同步打拍 多比特异步信号 1.异步FIFO2.保持…...
Avalonia常用小控件Menu
1.项目下载地址:https://gitee.com/confusedkitten/avalonia-demo 2.UI库Semi.Avalonia,项目地址 https://github.com/irihitech/Semi.Avalonia 样式预览: axaml代码 : <UserControl xmlns"https://github.com/avalo…...
steam游戏服务器如何选择
steam游戏平台现在在国内市场很吃香,当我们自己开发的游戏想要上架steam我们需要准备什么,在选择服务器的时候我们又需要考虑哪些因素呢,该怎样选择一款适合自己游戏的服务器是很关键的。 Steam专用服务器通常是指由游戏开发商提供的服务器&…...
电脑技巧:推荐一款桌面整理神器TidyTabs
目录 1、软件简介 2、软件功能介绍 3、总结 1、软件简介 TidyTabs是一款Windows应用程序,它可以将多个打开的窗口整理成一个选项卡式的界面,使得用户可以更加方便地切换和管理不同的窗口。 TidyTabs可以将多个窗口整合到一个主窗口中,类似…...
git合并分支-IDEA
有1个主分支,我从主分支拉取过来了,数据然后改好了,现在想合并到主分支上,并且将主分支的内容更新到我的分支下。用git怎么操作? 1.将主分支(master)的内容合并到我的分支(master-shi)中 在我的分支下执行 git merge master ID…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
密码学基础——SM4算法
博客主页:christine-rr-CSDN博客 专栏主页:密码学 📌 【今日更新】📌 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 编辑…...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
