算法排序算法
文章目录
- 快速排序
- [leetcode 215数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/)
- 分析
- 题解
- 快速排序
- 桶排序
- [leetcode 347 前K个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/)
- 分析
- 题解
快速排序
leetcode 215数组中的第K个最大元素
分析
对于这种“第K个元素”的问题,可以用快速选择,它是对快速排序的一种简化。快速排序采用分治思想,将数组分为两个子数组,每次划分数组都随机选择一个元素,小于该元素的在一个数组,大于该元素的在另一个数组。递归执行划分数组操作,直到数组全部完成排序。
而快速选择针对某个元素,它不要求对两个子数组排序,仅仅递归划分“第K个元素”在的那个子数组即可,直到获得“第K个元素”的位置。为了避免两个子数组,一个长度为1,一个长度为n-1的极端情况,每次划分数组时随机选择元素。
题解
class Solution {static Random random = new Random();public int findKthLargest(int[] nums, int k) {int n = nums.length;int target = n - k;int left = 0;int right = n - 1;while(true) {int pivot = partition(nums, left, right);if (pivot == target) {return nums[pivot];} else if (pivot < target) {left = pivot + 1;} else {right = pivot - 1;}}}private int partition(int[] nums, int left, int right) {int randomIndex = left + random.nextInt(right - left + 1);swap(nums, randomIndex, left);int l = left + 1;int r = right;while (true) {while (l <= r && nums[r] > nums[left] ) {r--;}while (l <= r && nums[l] < nums[left] ) {l++; }if (l >= r) {break;}swap(nums, l, r);l++;r--;}swap(nums, left, r);return r;}private void swap(int[] nums, int i1, int i2) {int temp = nums[i1];nums[i1] = nums[i2];nums[i2] = temp;}
}
快速排序
quickSort通过递归实现快速排序。
class Solution {static Random random = new Random();public void quickSort(int[] nums, int left, int right) {if (left < right) {int index = partition(nums, left, right);quickSort(nums, left, index - 1);quickSort(nums, index + 1, right);}}private int partition(int[] nums, int left, int right) {int randomIndex = left + random.nextInt(right - left + 1);swap(nums, randomIndex, left);int l = left + 1;int r = right;while (true) {while (l <= r && nums[r] > nums[left] ) {r--;}while (l <= r && nums[l] < nums[left] ) {l++; }if (l >= r) {break;}swap(nums, l, r);l++;r--;}swap(nums, left, r);return r;}private void swap(int[] nums, int i1, int i2) {int temp = nums[i1];nums[i1] = nums[i2];nums[i2] = temp;}
}
桶排序
leetcode 347 前K个高频元素
分析
首先统计元素频次,之后对频次建桶,桶里内容是该频次对应的元素们。最后根据频次高低返回K个元素。
题解
class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}List<Integer>[] list = new List[nums.length + 1];for (int num : map.keySet()) {int count = map.get(num);if (list[count] == null) {list[count] = new ArrayList<Integer>();}list[count].add(num);}int[] res = new int[k];int idx = 0;for (int i = list.length - 1; i >= 0 && idx < k; i--) {if (list[i] == null ) {continue;}while (!list[i].isEmpty()) {res[idx++] = list[i].getLast();list[i].removeLast();}}return res;}
}
相关文章:
算法排序算法
文章目录 快速排序[leetcode 215数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/)分析题解快速排序 桶排序[leetcode 347 前K个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/)分析题解 快速排序 leetcode 215数组…...
第3章 总线
总线的定义 为多个部件 分时共享 公共信息传送线路。 系统之间、模块之间、芯片内部用来传递信息信号线集合。 共享 总线上可连接多个部件 各部件间相互交换信息 都可通过总线来。 分时 同一时刻 总线上只能传 一个部件信息。 采用标准总线的优点 简化系统软硬件设计 从硬件角度…...
手机实时提取SIM卡打电话的信令声音-双卡手机来电如何获取哪一个卡的来电
手机实时提取SIM卡打电话的信令声音 --双卡手机来电如何获取哪一个卡的来电 一、前言 前面的篇章《手机实时提取SIM卡打电话的信令声音-智能拨号器的双SIM卡切换方案》中,我们论述了局域网SIP坐席通过手机外呼出去时,手机中主副卡的呼叫调度策略。 但…...
共阳极LED的控制与短路问题解析
共阳极LED的控制与短路问题解析 在电子电路中,LED(发光二极管)是最常见的元件之一。LED的连接方式分为共阳极和共阴极,不同的连接方式决定了LED的控制逻辑。本文将重点讲解共阳极LED的工作原理,并解答“为什么给1不会…...
华为消费级QLC SSD来了
近日,有关消息显示,华为的消费级SSD产品线,eKitStor Xtreme 200E系列,在韩国一家在线零售商处首次公开销售,引起了业界的广泛关注。 尽管华为已经涉足服务器级别的SSD制造多年,但直到今年6月才正式推出面向…...
liunx下载gitlab
1.地址: https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el7/ 安装 postfix 并启动 yum install postfix systemctl start postfix systemctl enable postfix ssh服务启动 systemctl enable sshd systemctl start sshd开放 ssh 以及 http 服务,…...
深度学习模型预测值集中在某一个值
深度学习模型,训练过程中,经常遇到预测的结果集中在某个值,而且在学习的过程中会变,样例如下。 主要有如下解决方案 1、更换relu ->tanh 或者其他激活函数 2、更改随机种子,估计是没有初始化好,或者调…...
Sqoop的使用
每个人的生活都是一个世界,即使最平凡的人也要为他那个世界的存在而战斗。 ——《平凡的世界》 目录 一、sqoop简介 1.1 导入流程 1.2 导出流程 二、使用sqoop 2.1 sqoop的常用参数 2.2 连接参数列表 2.3 操作hive表参数 2.4 其它参数 三、sqoop应用 - 导入…...
OpenGL ES 04 图片数据是怎么写入到对应纹理单元的
从指定路径加载图像并转换为 CGImage。获取图像的宽度和高度。创建一个 RGB 颜色空间。为图像数据分配内存。创建一个位图上下文并将图像绘制到上下文中。创建一个新的纹理对象并绑定到指定的纹理单元。指定二维纹理图像。释放分配的内存。设置纹理参数,包括放大和缩…...
C# 设计模式的六大原则(SOLID)
C# 设计模式的六大原则(SOLID) 引言 在面向对象编程中,设计模式提供了高效、可复用和可维护的代码结构。SOLID原则是软件设计中的一组重要原则,用于确保代码具有良好的可维护性、可扩展性和灵活性。SOLID是五个设计原则的首字母…...
数据库自增 id 过大导致前端时数据丢失
可以看到,前端响应参数是没有丢失精度的 但是在接受 axios 请求参数时出现了精度丢失 解决方案一:改变 axios 字符编码 axios.defaults.headers[Content-Type] application/json;charsetUTF-8; 未解决 解决方案二:手动使用 json.parse() …...
第二十六天 自然语言处理(NLP)词嵌入(Word2Vec、GloVe)
自然语言处理(NLP)中的词嵌入(Word2Vec、GloVe)技术,是NLP领域的重要组成部分,它们为词汇提供了高维空间到低维向量的映射,使得语义相似的词汇在向量空间中的距离更近。以下是对这些技术的详细解…...
MongoDB 固定集合
MongoDB 固定集合 MongoDB中的固定集合(Capped Collections)是一种具有固定大小的集合,当集合中的数据达到其最大大小时,它会自动覆盖最早的文档。这种类型的集合在MongoDB中用于实现高效的、固定大小的循环缓冲区。本文将详细介…...
数据结构9.3 - 文件基础(C++)
目录 1 打开文件字符读写关闭文件 上图源自:https://blog.csdn.net/LG1259156776/article/details/47035583 1 打开文件 法 1法 2ofstream file(path);ofstream file;file.open(path); #include<bits/stdc.h> using namespace std;int main() {char path[]…...
Leetcode 1254 Number of Closed Islands + Leetcode 1020 Number of Enclaves
Leetcode 1254 题意 给定一个m*n的矩阵含有0和1,1代表水,0代表陆地,岛屿是陆地的集合,如果一个岛屿和四个方向的边界相连,则不算封闭岛屿。求有多少个封闭的岛屿。 题目链接 https://leetcode.com/problems/number…...
Junit4单元测试快速上手
文章目录 POM依赖引入业务层测试代码Web层测试代码生成测试类文件 在工作中我用的最多的单元测试框架是Junit4。通常在写DAO、Service、Web层代码的时候都会进行单元测试,方便后续编码,前端甩锅。 POM依赖引入 <dependency><groupId>org.spr…...
U盘提示格式化?原因、恢复方案与预防措施全解析
一、U盘提示格式化现象概述 在日常使用U盘的过程中,我们有时会遇到一个令人头疼的问题——U盘插入电脑后,系统却弹出一个提示框,告知我们U盘需要格式化才能访问。这个提示往往伴随着数据的潜在丢失风险,让我们不禁为之心焦。U盘提…...
HTML——13.超链接
<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>超链接</title></head><body><!--超链接:从一个网页链接到另一个网页--><!--语法:<a href"淘宝网链接的地址"> 淘宝…...
vue中的设计模式
vue中使用了哪些设计模式 1. 观察者模式(Observer Pattern) 应用场景:Vue 的响应式系统核心就是观察者模式。 实现方式:通过 Object.defineProperty 或 Proxy 监听数据变化,当数据发生变化时,通知依赖的视…...
利用python将图片转换为pdf格式的多种方法,实现批量转换,内置模板代码,全网最全,超详细!!!
文章目录 前言1、img2pdf库的使用1.1 安装img2pdf库1.2 案例演示(模板代码) 2、Pillow库的使用2.1 pillow库的安装2.2 案例演示(模板代码) 3、PyMuPDF库的使用3.1 安装pymupdf库3.2 案例演示(模板代码)3.3 …...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
