牛客-寻找第K大、LeetCode215. 数组中的第K个最大元素【中等】

文章目录

  • 前言
  • 牛客-寻找第K大、LeetCode215. 数组中的第K个最大元素【中等】
    • 题目及类型
    • 思路
      • 思路1:大顶堆
      • 思路2:快排+二分+随机基准点

前言

博主所有博客文件目录索引:博客目录索引(持续更新)


牛客-寻找第K大、LeetCode215. 数组中的第K个最大元素【中等】

题目及类型

相同题目:215. 数组中的第K个最大元素

题目链接:寻找第K大

题目内容:有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。

类型:大顶堆、快排+二分


思路

思路1:大顶堆

class Solution {public int findKthLargest(int[] nums, int k) {if (nums == null || nums.length == 0) {return 0;}PriorityQueue<Integer> queue = new PriorityQueue<>(k, (o1, o2)->o2.compareTo(o1));for (int i = 0; i < nums.length; i++) {queue.offer(nums[i]);}while (k > 1) {queue.poll();k--;}return queue.poll();}
}

思路2:快排+二分+随机基准点

最佳思路:快排+二分+随机基准点。在快排的过程中不断的找到对应的基准点,然后以这个基准点比较k(基准点的左边是>该基准点的,这样我们才能将基准点的索引与第k大的索引来进行比较)

思路:快排+二分+随机基准点

复杂度分析:

  • 时间复杂度:O(n.logn)
  • 空间复杂度:O(n)

一个探索思路的过程:

import java.util.*;public class Solution {private static int res;Private static Random random = new Ramdom();public int findKth(int[] a, int n, int K) {quickSort(a, 0, n - 1, K);return res;}public void quickSort(int[] a, int l, int r, int K) {if (l > r) {return;}int mid = partition(a, l, r);//看这个基准点与K的位置是否相符if (mid + 1 == K) {res = a[mid];}else if (mid + 1 < K) {quickSort(a, mid + 1, r, K);}else {quickSort(a, 0, mid - 1, K);}}public int partition(int[] a, int l, int r) {int x = Math.abs(random.nextInt()) % (r - l + 1) + l;swap(a, l, x);int j = l;for (int i = l + 1; i <= r; i++) {if (a[i] >= a[l]) {j++;swap(a, i, j);}}//交换基准点swap(a, l, j);return j;}public void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}

不同的分块思路:

//方式一:
public int partition(int[] a, int l, int r) {int x = Math.abs(random.nextInt()) % (r - l + 1) + l;swap(a, l, x);int j = l;for (int i = l + 1; i <= r; i++) {if (a[i] >= a[l]) {j++;swap(a, i, j);}}//交换基准点swap(a, l, j);return j;
}//方式二:
public int partition(int[] a, int l, int r) {int v = a[l];int i = l + 1;int j = r;while (true) {//目标找到小于基准值的while (i <= r && a[i] > v ) {i++;}//目标找到大于基准值的//注意:这里j>=l+1while (j >= l + 1 && a[j] < v) {j--;}if (i > j) {break;}swap(a, i, j);i++;j--;}//交换基准点swap(a, l, j);return j;
}

写的好快排方式:

class Solution {//大顶堆找public int findKthLargest(int[] nums, int k) {//由于找的是第k大,那么从小到大的顺序就是kreturn quickFind(nums, 0, nums.length - 1, nums.length - k);}public int quickFind(int[] nums, int left, int right, int k) {//基准点int x = nums[left];if (left == right) return nums[k];int i = left - 1, j = right + 1;while (i < j) {do i ++; while (nums[i] < x);do j --; while (nums[j] > x);//交换if (i < j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}//若是寻找的位置<=j,那么左范围进行递归if (k <= j) {return quickFind(nums, left, j, k);}else { //右范围进行递归return quickFind(nums, j + 1, right, k);}}}

image-20240115204027224


整理者:长路 时间:2024.1.14-15

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

云计算概述(发展过程、定义、发展阶段、云计算榜单)(一)

云计算概述&#xff08;一&#xff09; &#xff08;发展过程、定义、发展阶段、云计算榜单&#xff09; 本文目录&#xff1a; 零、00时光宝盒 一、前言 二、云计算的发展过程 三、云计算的定义 四、云计算发展阶段 五、云计算公司榜单看云计算兴衰 六、参考资料 零、0…

小程序中滚动字幕

需求&#xff1a;在录像时需要在屏幕上提示字幕&#xff0c;整体匀速向上滚动 html部分&#xff1a; <view class"subtitles_main"><view style"font-size:34rpx;color: #fff;line-height: 60rpx;" animation"{{animation}}">人生的…

Linux工具-搭建文件服务器

当我们使用linux系统作为开发环境时&#xff0c;经常需要在Linux系统之间、Linux和Windows之间传输文件。 对少量文件进行传输时&#xff0c;可以使用scp工具在两台主机之间实现文件传输&#xff1a; rootubuntu:~$ ssh --help unknown option -- - usage: ssh [-46AaCfGgKkMN…

五种嵌入式经典通信总线协议

一.先前知识 1.并行与串行 并行通信和串行通信是两种不同的数据传输方式&#xff1a; 并行通信&#xff1a;并行通信是指在同一时间使用多条并行传输的线路传输多个比特的数据。每个比特使用独立的线路进行传输&#xff0c;同时进行。这样可以在一个时钟周期内传输多个比特&…

nova组件讲解和glance对接swift

1、openstack架构 &#xff08;1&#xff09;openstack是一种SOA架构&#xff08;微服务就是从这种架构中剥离出来的&#xff09; &#xff08;2&#xff09;这种SOA架构&#xff0c;就是把每个服务独立成一个组件&#xff0c;每个组件通过定义好的api接口进行互通 &#xff…

复合机器人作为一种新型的智能制造装备高效、精准和灵活的生产方式

随着汽车制造业的快速发展&#xff0c;对于高效、精准和灵活的生产方式需求日益增强。复合机器人作为一种新型的智能制造装备&#xff0c;以其独特的优势在汽车制造中发挥着越来越重要的作用。因此&#xff0c;富唯智能顺应时代的发展趋势&#xff0c;研发出了ICR系列的复合机器…

京东年度数据报告-2023全年度笔记本十大热门品牌销量(销额)榜单

2023年度&#xff0c;在电脑办公市场整体销售下滑的环境下&#xff0c;笔记本市场的整体销售也不景气。 根据鲸参谋平台的数据显示&#xff0c;京东平台上笔记本的年度销量为650万&#xff0c;同比下滑约16%&#xff1b;销售额约为330亿&#xff0c;同比下滑约19%。同时&#…

CF1178F2 Long Colorful Strip 题解 搜索

Long Colorful Strip 传送门 题面翻译 题目描述 这是 F 题的第二个子任务。F1 和 F2 的区别仅在对于 m m m 和时间的限制上 有 n 1 n1 n1 种颜色标号从 0 0 0 到 n n n&#xff0c;我们有一条全部染成颜色 0 0 0 的长为 m m m 的纸带。 Alice 拿着刷子通过以下的过…

uniapp微信小程序投票系统实战 (SpringBoot2+vue3.2+element plus ) -投票帖子明细实现

锋哥原创的uniapp微信小程序投票系统实战&#xff1a; uniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )_哔哩哔哩_bilibiliuniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )共计21条视频…

经典目标检测YOLO系列(一)复现YOLOV1(5)模型的训练及验证

经典目标检测YOLO系列(一)复现YOLOV1(5)模型的训练及验证 之前&#xff0c;我们依据《YOLO目标检测》(ISBN:9787115627094)一书&#xff0c;提出了新的YOLOV1架构&#xff0c;继续按照此书进行YOLOV1的复现。 经典目标检测YOLO系列(一)YOLOV1的复现(1)总体架构 经典目标检测Y…

Python Flask教程

Flask Doc: https://rest-apis-flask.teclado.com/docs/course_intro/what_is_rest_api/Github: https://github.com/tecladocode/rest-apis-flask-python 1. 最简单的应用 最小应用 from flask import Flaskapp Flask(__name__)app.route("/") def hello_world()…

18 串口通讯

文章目录 18.0 前言18.1 串口通讯协议简介18.1.1 物理层 18.2 RT1052 的 LPUART 简介18.3 UART 功能框图18.3.1 中断控制 18.4 UART 初始化结构体详解18.4.1 baudRate_Bps18.4.2 parityMode18.4.3 dataBitsCount18.4.4 isMsb18.4.5 stopBitCount18.4.6 txFifoWatermark与rxFifo…

Kubernetes 集群管理—日志架构

日志架构 应用日志可以让你了解应用内部的运行状况。日志对调试问题和监控集群活动非常有用。 大部分现代化应用都有某种日志记录机制。同样地&#xff0c;容器引擎也被设计成支持日志记录。 针对容器化应用&#xff0c;最简单且最广泛采用的日志记录方式就是写入标准输出和标…

RIP【新华三与华为区别】

【介绍】 rip分为rip 1 与 rip 2 &#xff0c;rip 2 是对 rip 1 的一种升级&#xff0c;rip 2 可以进行认证等功能 【命令】 新华三&#xff1a; [HC3-R1] rip #启用rip [HC3-R1-rip] version 2 #告知rip 版本号 [HC3-R1-rip] network 192.168.1.0 #宣告其网段 [HC3-R1-rip] …

ES分词器

Analysis&#xff1a;文本分析是把全文本转换一系列单词的过程&#xff0c;也叫分词。Analysis是通过Analyzer(分词器)来实现的。 1.Analyzer组成 注意&#xff1a;在ES中默认使用标准分词器&#xff1a;StandardAnalyzer。特点是&#xff1a;中文是单字分词&#xff0c;英文是…

Docker 容器之间的互相通信

Docker容器之间的互相通信 步骤一&#xff1a;创建自定义网络 首先&#xff0c;我们需要创建一个自定义网络&#xff0c;以便容器可以连接到这个网络上&#xff0c;从而实现互相通信。在命令行中执行以下命令&#xff1a; # 创建 docker network create ddz # 查看 docker n…

costmap_2d包介绍

文章目录 一. costmap_2d包介绍二. Costmap包的执行入口-- move_base中调用三. Costmap包的初始化以及维护3.1 Costmap2DROS类3.1.1 构造函数 Costmap2DROS::Costmap2DROS3.1.2 地图更新线程 Costmap2DROS::mapUpdateLoop3.1.3 地图更新 Costmap2DROS::updateMap()3.1.4 激活各…

openssl3.2 - 在VS2019下源码调试openssl.exe

文章目录 openssl3.2 - 在VS2019下源码调试openssl.exe概述笔记先看一个用.bat调用openssl干活的实例VS2019调试参数设置设置 - 命令参数设置 - 工作目录设置 - 环境变量将命令行中需要的文件拷贝到exe目录单步调试备注END openssl3.2 - 在VS2019下源码调试openssl.exe 概述 …

多租户体系实现

文章目录 核心思路方案选择设计考量安全性扩展性通用性易用性 具体实现租户信息透传透传变量名命名规范应用内透传应用间透传 数据层租户隔离MySQL存储方案&#xff1a;多租户Mybatis插件Mybatis插件特点使用多租户Mybatis插件的优势参考文档 应用场景 经过工作中的一处场景启发…

PLC编程中ST语言操作符的使用方法

ST&#xff08;Structured Text&#xff09;语言操作符主要用于PLC编程&#xff0c;主要包括算术运算符、比较运算符和逻辑运算符等。 算术运算符包括加&#xff08;&#xff09;、减&#xff08;-&#xff09;、乘&#xff08;*&#xff09;、除&#xff08;/&#xff09;和指…