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…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
热烈祝贺埃文科技正式加入可信数据空间发展联盟
2025年4月29日,在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上,可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞,强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...
论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...
【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解
一、前言 在HarmonyOS 5的应用开发模型中,featureAbility是旧版FA模型(Feature Ability)的用法,Stage模型已采用全新的应用架构,推荐使用组件化的上下文获取方式,而非依赖featureAbility。 FA大概是API7之…...
