LeetCode_101

千奇百怪的排序算法

快速排序

采用左闭右开的二分写法

 归并排序

 插入排序

 冒泡排序

 选择排序

 以上代码的调用方式:

 快速选择

在一个未排序的数组中,找到第 k 大的数字

快速选择一般用于求解 k-th Element 问题,可以在 O(n) 时间复杂度,O(1) 空间复杂度完成求 解工作。快速选择的实现和快速排序相似,不过只需要找到第 k 大的枢(pivot)即可,不需要对 其左右再进行排序。与快速排序一样,快速选择一般需要先打乱数组,否则最坏情况下时间复杂 度为 O(n 2 )

第K个数算法-CSDN博客

参考之前写的博客

桶排序

 桶排序的意思是为每个值设立一个桶,桶内记录这个值出现的次数(或其它属 性),然后对桶进行排序。针对样例来说,我们先通过桶排序得到四个桶 [1,2,3,4],它们的值分别 为 [4,2,1,1],表示每个数字出现的次数。

 紧接着,我们对桶的频次进行排序,前 k 大个桶即是前 k 个频繁的数。这里我们可以使用各种 排序算法,甚至可以再进行一次桶排序,把每个旧桶根据频次放在不同的新桶内。针对样例来说, 因为目前最大的频次是 4,我们建立 [1,2,3,4] 四个新桶,它们分别放入的旧桶为 [[3,4],[2],[],[1]], 表示不同数字出现的频率。最后,我们从后往前遍历,直到找到 k 个旧桶。

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp); 

 优先队列的定义

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;
static bool cmp(pair<int, int>& m, pair<int, int>& n) {
    return m.second > n.second;
}

std::priority_queue 是一个模板类,有三个模板类型参数,分别是:

  1. 参数1: 优先级队列的元素类型 T ,例如问题里第一个例子,元素类型 T 是 std::pair<int,int> ,后面两个例子,元素类型 T 是 int
  2. 参数2: 优先级队列内部具体用那种容器(Container) 存储参数1指定的元素类型,例如问题里的 vector< pair<int,int> > 和 vector<int>。实际上,第2个模板参数是有默认类型参数的,默认类型参数是 vector<T> ,T 取决于参数1指定的类型是什么。
  3. 参数3: 参数3需要指定一个实现了 operator< 操作符的类(叫做仿函数或者函数对象,实际上就是类,只是调用时写起来像函数一样),比较操作符的实现符合 严格弱顺序 strict weak order  语义,请参考资料3。模板参数3也是有默认类型,默认是 std::less<typename Container::value_type> ,其中 Container 指的是参数2,Container::value_type 指的是参数2类内部的声明的其元素值的类型。
  4. 最后,decltype 用于类型自动推断,传入&cmp函数指针,decltype自动推断出第3个模版参数类型应该是什么。总的来说,如果你的元素类型已经符合严格弱顺序排序,只要自定优先级队列的第1个模版参数即可。

 参考博客:

c++优先队列priority_queue(自定义比较函数)_c++优先队列自定义比较_菊头蝙蝠的博客-CSDN博客

c++优先队列(priority_queue)用法详解_吕白_的博客-CSDN博客 

 练习

 排序也可以这样写

sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
            return a.second > b.second;
        });

 一切皆可搜索

深度优先搜索和广度优先搜索是两种最常见的优先搜索方法,它们被广泛地运用在图和树等 结构中进行搜索。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/10623.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Unix、UTC、GPS时间戳及转换

UTC时间 UTC时间的英文全称&#xff1a;Universal Time Coordinated&#xff0c;中文名称&#xff1a;协调世界时。俗的理解为&#xff0c;这个时间是全世界通用的&#xff0c;即全世界都公用的一个时间。可以认为格林威治时间就是时间协调时间&#xff08;GMTUTC&#xff09;&…

测试名词介绍

测试名词介绍一&#xff1a;敏捷测试1. 定义&#xff1a;2. 敏捷测试的核心&#xff1a;3. 敏捷测试的8大原则和传统测试的区别二&#xff1a;测试名词介绍瀑布模型回归测试Alpha测试Beta测试性能测试白盒测试黑盒测试灰盒测试三&#xff1a;测试流程单元测试 (unit test)集成测…

ChatGPT想干掉开发人员,做梦去吧

很多人都发现ChatGPT可以做一些代码相关的工作&#xff0c;不仅可以写一些基础的类似python、java、js的代码段&#xff0c;还可以做一定量的调优&#xff0c;于是就开始担忧起来&#xff0c;到哪天我的开发工作会不会被ChatGPT这个工具给取代了&#xff1f; 目录 1. ChatGPT…

前 K 个高频元素(力扣刷题代码随想录刷题)

给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 思路&#xff1a; 要统计元素出现频率对频率排序找出前K个高频元素首先统计元素出现的频率&#xff0c;这一类的问题可以使用map来进行统计。 然后是对频率…

【血泪建议】软件测试岗位现状,可惜之前没人告诉我,肠子都晦青了....

谈到现状&#xff0c;国内的软件测试行情目前呈现了两极分化的极端情况。 一个是早期的手工测试人员吐槽工作不好做&#xff0c;即使有工作也是外包&#xff0c;而且薪资太低&#xff1b;一方面是很多互联网企业感叹自动化测试人才难找&#xff0c;有技术的自动化测试工程师&a…

批量自动翻译软件-准确的翻译软件

现代社会&#xff0c;在全球化背景下&#xff0c;语言障碍是碍企业发展的主要因素之一。而翻译软件的出现&#xff0c;为人们跨越语言障碍带来了新的解决方案。针对翻译需要大量文字内容的情况&#xff0c;有一些能翻译大量文字的翻译软件&#xff1a; 147CGPT翻译软件特点&…

面试篇-揭开Spring Bean加载的神秘面纱

SpringBean加载完整过程 启动spring容器&#xff08;创建beanfactory&#xff09;->加载配置(注解、xml)->实例化bean(执行构造方法)->注入依赖->初始化bean&#xff08;设置属性值&#xff09;->使用->销毁 解析和读取 XML 配置文件或注解配置类&#xff0…

【C++基础】引用(引用的概念;引用的特性;常引用;使用场景:做输出型参数、大对象传参、做输出型返回值、返回大对象的引用);引用和指针的区别)

六、引用 6.1 引用的概念 引用不是新定义一个变量&#xff0c;而是给已存在变量取了一个别名&#xff0c;编译器不会为引用变量开辟内存空间&#xff0c;它和它引用的变量共用同一块内存空间。&#xff08;语法上&#xff09; 格式&#xff1a;类型& 引用变量名(对象名) …

用vscode运行Java程序初体验

最近开始学习Java编程了&#xff0c;以前学习过C、C 、Python&#xff0c;主要用微软的visual studio code来运行python程序&#xff0c;于是就尝试了用vscode来运行java代码&#xff0c;记录一下使用的经验&#xff0c;帮助大家少走弯路。 安装了Java的集成编辑器IDE "Ec…

Docker环境安装

Docker环境安装Docker简介Docker工作原理Docker的应用场景Docker 的优点CentOS Docker 安装与配置Docker 安装Docker 配置Docker容器概念Docker容器操作拉取镜像删除镜像容器相关命令创建并启动容器停止和恢复容器删除容器Docker简介 Docker 是一个开源的应用容器引擎&#xf…

不卷不成魔,新时代的IT人员更需要卷,不卷不成活

简介 从2022年开始至今&#xff0c;IT界发生了很多巨大的变革带来了许多巨大的变化。 这些变革、这些变化导致了有人欢喜有人悲、有人迷茫有人焦虑。1年半来&#xff0c;迷茫、焦虑、精神内耗了也都差不多了&#xff0c;大家都已经认识到了现实&#xff0c;作为凡人的我们所能…

【防止恶意用户注册】-- 手机在网状态 API 的防欺诈应用解析

简介 手机在网状态 API 支持传入手机号码&#xff0c;查询手机号在网状态&#xff0c;返回在网、在网不可用、不在网&#xff08;销号/未启用/停机&#xff09;等多种状态&#xff0c;查询手机号在网状态之后&#xff0c;可以根据具体的业务需求来进行不同的处理。 本文主要介…

由libunifex来看Executor的任务构建

前言 之前的一篇文章讲述了future的优缺点&#xff0c;以及future的组合性&#xff0c;其中也讲述了构建任务DAG一些问题&#xff0c;同时给出了比较好的方案则是Executor。 Executor还未进入标准&#xff08;C23&#xff09;&#xff0c;Executor拥有惰性构建及良好的抽象模型…

c/c++:windows平台下依赖的动态库,c底层是汇编语言,程序断点调试,反汇编,vs快捷键

c/c&#xff1a;windows平台下依赖的动态库&#xff0c;c底层是汇编语言&#xff0c;程序断点调试&#xff0c;反汇编&#xff0c;vs快捷键 2022找工作是学历、能力和运气的超强结合体&#xff0c;遇到寒冬&#xff0c;大厂不招人&#xff0c;此时学会c的话&#xff0c; 我所知…

20230412-使用STM32实现内部flash模拟U盘

最近用STM32F103CBT6搞了个U盘功能 ​ 工程师干了几年后&#xff0c;基本会有小外包的生活&#xff0c;算是赚外快吧&#xff0c;搞小钱改善伙食&#xff0c;嘻嘻。。。。 ​ 最近有个客户找到我&#xff0c;说是否通过ST的单片机搞个U盘功能&#xff0c;有些文件通过U盘拖拽…

005:Mapbox GL添加全屏显示功能

第005个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中添加全屏显示功能 。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共60行)相关API参考:专栏目标示例效果 配置方式 1)查看基础设置:https://…

1~3年的测试工程师薪资陷入了瓶颈期,如何突破自己实现涨薪?

对于技术人员而言&#xff0c;职业规划一般分为两个方向&#xff1a;做技术、做管理。进入软件测试行业的新人都会从最基础的执行开始&#xff0c;然后是基本的功能测试。 随后大家会根据个人职业发展来进一步细化&#xff0c;有的走管理路线&#xff0c;成为主管、经理、项目…

Python 小型项目大全 76~81

七十六、井字棋 原文&#xff1a;http://inventwithpython.com/bigbookpython/project76.html 井字棋是一种在3 3网格上玩的经典纸笔游戏。玩家轮流放置 X 或 O 标记&#xff0c;试图连续获得三个。大多数井字棋都以平局告终&#xff0c;但如果你的对手不小心&#xff0c;你也…

AI 时代,提示词便是生产力

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;蚂蚁集团高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《EffectiveJava》独家解析》专栏作者。 热门文章推荐…

瑞芯微RK3568核心板强在何处?

RK3568核心板产品简介 RK3568核心板是武汉万象奥科基于瑞芯微Rockchip的RK3568设计的一款高性能核心板。该处理器集成了最新的高性能CPU、GPU&#xff0c;并拥有丰富的接口&#xff0c;非常适用于工业自动化控制、人机界面、中小型医疗分析器、电力等多种行业应用。 HD-RK3568-…