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

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 &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a;nums [3,2,3] 输出&#xff1a;3 示例 …...

FATFS f_printf 如何支持写入浮点数据。

参考原子和网上的移植最新的fatfs系统后,挂载打开文件始终返回13错误代码,在自己的项目中移植最新的fatfs0.15版本解决问题,使用f_printf能成功进行浮点数据写入了 参考的文章如下: https://zhuanlan.zhihu.com/p/444427537 问题描述 在使用fatfs的f_printf向文件.csv中写入…...

postman忘记密码提交没响应

现象&#xff1a;通过客户端进到账户页面一直无响应&#xff0c;可copy the url 到浏览器进入页面&#xff0c;使用浏览器提交几次还是没响应。 实测有用方法&#xff1a; 1、通过手机进入官网 https://www.getpostman.com &#xff0c;找到忘记密码入口。 2、多提交几次后&…...

初学vue,想自己找个中长期小型项目练练手,应该做什么?

前言 可以试着做一两个完整的后台管理项目后再去做其他的&#xff0c;下面推荐一些github上的vue后台管理的项目&#xff0c;可以自己选择性的练一下手 Vue2 1、iview-admin Star: 16.4k 基于 iview组件库开发的一款后台管理系统框架&#xff0c;提供了一系列的强大组件和基…...

【牛客面试必刷TOP101】Day11.BM63 跳台阶和 BM67 不同路径的数目(一)

作者简介&#xff1a;大家好&#xff0c;我是未央&#xff1b; 博客首页&#xff1a;未央.303 系列专栏&#xff1a;牛客面试必刷TOP101 每日一句&#xff1a;人的一生&#xff0c;可以有所作为的时机只有一次&#xff0c;那就是现在&#xff01;&#xff01;&#xff01;&…...

[NOIP 2022] 建造军营 题解

题目 P1 边双缩点 观察样例二&#xff0c;可以发现边双内的边可选可不选。由此考虑边双缩点&#xff0c;Tarjan 找桥即可&#xff0c;缩点后变成一棵树。 P2 设计状态 用最终合法答案形态截这颗树&#xff0c;设计 f u f_u fu​ 表示 u u u 子树内非空&#xff0c;且子树…...

射频识别技术(RFID)在智能制造模具管理中的应用

背景介绍 模具是工业生产的核心装备&#xff0c;被誉为“工业之母”&#xff0c;广泛应用于机械、汽车、轻工、电子、化工、冶金、建材等各个行业&#xff0c;是制造加工企业的重要资产&#xff0c;然而&#xff0c;传统的人工纸质记录方式已无法满足模具管理的需求&#xff0…...

奖品定制经营商城小程序的作用是什么

奖品是激励人员团体很好的方式&#xff0c;也是荣誉象征&#xff0c;奖牌、奖杯、高端礼盒等&#xff0c;同时市场中团体非常多&#xff0c;其需求也是很多&#xff0c;尤其定制方面&#xff0c;就更是不用说。 对奖品定制企业来说&#xff0c;除了线下门店获客经营外&#xf…...

深度学习常用脚本总结

&#x1f468;‍&#x1f4bb;个人简介&#xff1a; 深度学习图像领域工作者 &#x1f389;工作总结链接&#xff1a;https://blog.csdn.net/qq_28949847/article/details/128552785 链接中主要是个人工作的总结&#xff0c;每个链接都是一些常用demo&#xff0c…...

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&#xff0c;输入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 平台即服务 快速交付→ 快&#xff1a;自己去干、有结果、事事有回音、持续改进 单体架构——》垂直架构——》面向服务架构——》微服务架构&#xff08;分布式&#xf…...

JDK安装详细教程

JDK安装详细教程 国内大多数使用的是1.8的版本&#xff0c;对于初学者来说这个版本很友善&#xff0c;不过由于我安装过了1.8&#xff0c;所以我这里演示JDK21 的安装&#xff0c;过程并无区别&#xff0c;只在下载时注意选择1.8版本。1.8就是JDK8. 文章目录 JDK安装详细教程一…...

vulnhub_Fowsniff靶机渗透测试

Fowsniff靶机 靶机地址&#xff1a;https://www.vulnhub.com/entry/fowsniff-1,262/ 文章目录 Fowsniff靶机信息收集web渗透密码碰撞POP3邮件服务器渗透获取权限权限提升靶机总结 信息收集 通过nmap扫描&#xff0c;靶机开放22 80 110 143端口&#xff0c;110是pop3邮件服务…...

FPGA面试题(3)

一.FPGA和CPLD区别 FPGA&#xff1a;现场可编程门阵列CPLD&#xff1a;复杂可编程逻辑器件 二.多位异步信号如何同步 单比特异步信号 慢时钟域->快时钟域&#xff1a;同步打拍快时钟域->慢时钟域&#xff1a;先拓展位宽再同步打拍 多比特异步信号 1.异步FIFO2.保持…...

Avalonia常用小控件Menu

1.项目下载地址&#xff1a;https://gitee.com/confusedkitten/avalonia-demo 2.UI库Semi.Avalonia&#xff0c;项目地址 https://github.com/irihitech/Semi.Avalonia 样式预览&#xff1a; axaml代码 &#xff1a; <UserControl xmlns"https://github.com/avalo…...

steam游戏服务器如何选择

steam游戏平台现在在国内市场很吃香&#xff0c;当我们自己开发的游戏想要上架steam我们需要准备什么&#xff0c;在选择服务器的时候我们又需要考虑哪些因素呢&#xff0c;该怎样选择一款适合自己游戏的服务器是很关键的。 Steam专用服务器通常是指由游戏开发商提供的服务器&…...

电脑技巧:推荐一款桌面整理神器TidyTabs

目录 1、软件简介 2、软件功能介绍 3、总结 1、软件简介 TidyTabs是一款Windows应用程序&#xff0c;它可以将多个打开的窗口整理成一个选项卡式的界面&#xff0c;使得用户可以更加方便地切换和管理不同的窗口。 TidyTabs可以将多个窗口整合到一个主窗口中&#xff0c;类似…...

git合并分支-IDEA

有1个主分支&#xff0c;我从主分支拉取过来了&#xff0c;数据然后改好了&#xff0c;现在想合并到主分支上&#xff0c;并且将主分支的内容更新到我的分支下。用git怎么操作? 1.将主分支(master)的内容合并到我的分支(master-shi)中 在我的分支下执行 git merge master ID…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

6.9-QT模拟计算器

源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...