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…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
