LeetCode[中等] 215. 数组中的第 K 个最大元素

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路:基于快排改进的快速选择算法

  • 分解: 将数组 a[l⋯r] 「划分」成两个子数组 a[l⋯q−1]、a[q+1⋯r],使得 a[l⋯q−1] 中的每个元素小于等于 a[q],且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。其中,计算下标 q 也是「划分」过程的一部分。
  • 解决: 通过递归调用快速排序,对子数组 a[l⋯q−1] 和 a[q+1⋯r] 进行排序。
  • 合并: 因为子数组都是原址排序的,所以不需要进行合并操作,a[l⋯r] 已经有序。
  • 上文中提到的 「划分」 过程是:从子数组 a[l⋯r] 中选择任意一个元素 x 作为主元,调整子数组的元素使得左边的元素都小于等于它,右边的元素都大于等于它, x 的最终位置就是 q。

由此可以发现每次经过「划分」操作后,我们一定可以确定一个元素的最终位置,即 x 的最终位置为 q,并且保证 a[l⋯q−1] 中的每个元素小于等于 a[q],且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。所以只要某次划分的 q 为倒数第 k 个下标的时候,我们就已经找到了答案。我们只关心这一点,至于 a[l⋯q−1] 和 a[q+1⋯r] 是否是有序的,我们不关心。

在分解的过程当中,我们会对子数组进行划分,如果划分得到的 q 正好就是我们需要的下标,就直接返回 a[q];否则,如果 q 比目标下标小,就递归右子区间,否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间,提高了时间效率。这就是「快速选择」算法。

平均情况下,快速选择算法在每次分区之后都可以排除数组中的一半元素,递归调用层数是 O(logn),时间复杂度是 O(n),空间复杂度是 O(logn)。最差情况下,快速选择算法在每次分区时选择的基准元素都是数组中的最小值或最大值,递归调用层数是 O(n),时间复杂度是 O(n^{2}),空间复杂度是 O(n)。

使用随机选择基准元素的做法可以最大程度避免最差情况的发生,达到 O(n) 的时间复杂度。

public class Solution {Random random = new Random();public int FindKthLargest(int[] nums, int k) {int right = nums.Length;return Select(nums, k - 1, 0, right - 1);}public int Select(int[] nums, int index, int left, int right){int pivotIndex = QuickSort(nums, left, right);if(pivotIndex == index)return nums[pivotIndex];else if(pivotIndex > index)return Select(nums, index, left, pivotIndex - 1);elsereturn Select(nums, index, pivotIndex + 1, right);}public int QuickSort(int[] nums, int left, int right){int randomIndex = left + random.Next(right - left + 1);int tempLeft = left + 1, tempRight = right;Swap(nums, randomIndex, left);int pivot = nums[left];while(tempLeft < tempRight){while(tempLeft < tempRight &&nums[tempRight] < pivot){tempRight--;//从右往左遍历,直到遇到大于等于基准元素的元素}while(tempLeft < tempRight &&nums[tempLeft] >= pivot){tempLeft++;//从左往右遍历,直到遇到小于基准元素的元素}if(tempLeft < tempRight)Swap(nums, tempLeft, tempRight);}while(tempRight > left && nums[tempRight] < pivot)//找基准元素应该在的位置tempRight--;if(tempRight > left)Swap(nums, left, tempRight);return tempRight;}public void Swap(int[] nums, int index1, int index2){int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

复杂度分析

  • 时间复杂度:平均情况是 O(n),最差情况是 O(n^2),其中 n 是数组 nums 的长度。快速选择算法的平均时间复杂度是 O(n),最差时间复杂度是 O(n^2)。
  • 空间复杂度:平均情况是 O(logn),最差情况是 O(n),其中 n 是数组 nums 的长度。空间复杂度取决于递归调用层数。平均情况下,递归调用层数是 O(logn),快速选择算法的空间复杂度是 O(logn)。最差情况下,递归调用层数是 O(n),快速选择算法的空间复杂度是 O(n)。

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

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

相关文章

【云原生安全篇】一文掌握Harbor集成Trivy应用实践

【云原生安全篇】一文掌握Harbor集成Trivy应用实践 目录 1 概念 1.1 什么是 Harbor 和 Trivy&#xff1f; 1.1.1 Harbor 1.1.2 Trivy 1.2 Harbor 与 Trivy 的关系 Trivy 在 Harbor 中的作用&#xff1a; 1.3 镜像扫描工作流程 2 实战案例&#xff1a;在Harbor 配置 Trivy …

初识模版!!

初识模版 1.泛型编程1.1 如何实现一个交换函数呢&#xff08;使得所有数据都可以交换&#xff09;&#xff1f;1.2 那可以不可以让编译器根据不同的类型利用该模子来生成代码呢&#xff1f; 2.模版类型2.1 模版概念2.2 函数模版的原理2.3 函数模板的实例化2.4 模板参数的匹配原…

Windows上创建批处理.bat文件并且注册为开机自启(Python-web微服务)

1. winodws桌面点击创建文本文件 &#xff08;文件名称.txt&#xff09; 2. 将如下代码写入txt文件中 echo off if "%1""h" goto begin start mshta vbscript:createobject("wscript.shell").run("""%~nx0"" h"…

(七)使用SoapUI工具调用WebAPI

1.调用一个无参数的GET请求 [HttpGet(Name "GetWeatherForecast")]public IEnumerable<WeatherForecast> Get(){return Enumerable.Range(1, 5).Select(index > new WeatherForecast{Date DateTime.Now.AddDays(index),TemperatureC Random.Shared.Next(…

科研绘图系列:R语言箱线图(boxplot)

文章目录 介绍加载R包导入数据画图1画图2合并图形系统信息介绍 箱线图展示不同分组的数据分布差异。 加载R包 library(here) library("tidyverse") library("ggpubr") library("scales")

【工具】Windows|两款开源桌面窗口管理小工具Deskpins和WindowTop

总结 Deskpins 功能单一&#xff0c;拖到窗口上窗口就可以置顶并且标记钉子标签&#xff0c;大小 104 KB&#xff0c;开源位置&#xff1a;https://github.com/thewhitegrizzli/DeskPins/releases WindowTop 功能完善全面强大&#xff0c;包括透明度、置顶、选区置顶等一系列功…

如何查看Android设备的dpi

adb shell getprop ro.sf.lcd_density adb shell cat /system/build.prop > build_prop.txt shell cat system/build.prop 结果&#xff1a;参考&#xff1a; 如何查看Android设备的dpi_安卓 查看手机dpi-CSDN博客

ElementUI 用span-method实现循环el-table组件的合并行功能

需要把指定列的相同数据合并起来&#xff08;项目中用的是updateTime&#xff09; 后端返回的数据格式&#xff1a; html&#xff1a; <el-tab-pane label"执行记录概览" name"fourth" v-loading"loading"><el-timeline v-if"re…

windows安装Anaconda教程

一、简介 Anaconda 是一个开源的 Python 和 R 语言的分发平台&#xff0c;专为科学计算和数据分析设计。它包含了包管理器 Conda&#xff0c;可以方便地安装和管理库、环境和依赖项。此外&#xff0c;Anaconda 还附带了许多数据科学工具和库&#xff0c;如 Jupyter Notebook 和…

Ubuntu截图工具flameshot

最近在使用香橙派做一些东西&#xff0c;有些内容需要截图记录&#xff0c;这里记录一下截图工具的安装和使用过程&#xff0c;方便以后查阅。 Ubuntu截图工具flameshot flameshot 简介flameshot 安装flameshot 相关命令 flameshot 简介 linux系统里面最好用的截屏工具支持图形…

el-table的树形结构结合多选框使用,实现单选父子联动,全选,反选功能

<template><div><el-table:data"tableData":row-key"rowKey":default-expand-all"defaultExpandAll":tree-props"treeProps"><!-- 开启树形多选 --><el-table-column v-if"showSelection" width…

[Matplotlib教程] 02 折线图、柱状图、散点图教程

基于MFCC和CNN的语音情感识别 2 折线图、柱状图、散点图2.1 折线图2.1.1 简单折线图2.1.1 线形和Markevery2.1.2 带误差棒的折线图2.1.3 区间填充和透明度 2.2 柱状图2.2.1 分组柱状图2.2.2 堆叠柱状图2.2.3 横向柱状图 2.3 散点图 我们的网站是 菜码编程&#xff0c;我们的q群…

Altium Designer(AD)百度云下载与安装(附安装步骤)

在我们日常使用当中&#xff0c;Altium designer常常也被简称为AD&#xff0c;是一款一体化的电子产品开发系统软件&#xff0c;主要运行在Windows操作系统上。 我们通过Altium designer把原理图设计、电路仿真、PCB绘制编辑、拓扑逻辑自动布线、信号完整性分析和设计输出等技…

毕业设计选题:基于ssm+vue+uniapp的捷邻小程序

开发语言&#xff1a;Java框架&#xff1a;ssmuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;M…

多层感知机paddle

多层感知机——paddle部分 本文部分为paddle框架以及部分理论分析&#xff0c;torch框架对应代码可见多层感知机 import paddle print("paddle version:",paddle.__version__)paddle version: 2.6.1多层感知机&#xff08;MLP&#xff0c;也称为神经网络&#xff0…

web基础—dvwa靶场(十)XSS

XSS(DOM) 跨站点脚本&#xff08;XSS&#xff09;攻击是一种注入攻击&#xff0c;恶意脚本会被注入到可信的网站中。当攻击者使用 web 应用程序将恶意代码&#xff08;通常以浏览器端脚本的形式&#xff09;发送给其他最终用户时&#xff0c;就会发生 XSS 攻击。允许这些攻击成…

【3D打印】使用simplify 3D切片更改Gcode手动断电续打、掉电、未打完继续打印、补救

一、问题描述 有些时候会遇到3D打印机没料但机器还在继续打、掉电重启后未正常恢复打印、挤出机端没有料但断料检测未触发等情况。我们又不想打印放弃&#xff0c;但又想继续之前的进度打印。 这时候我们需要更改3D打印文件的Gcode参数来进行继续打印。 至于什么是Gcode&…

SQL - 基础语法

SQL作为一种操作命令集, 以其丰富的功能受到业内人士的广泛欢迎, 成为提升数据库操作效率的保障。SQL Server数据库的应用&#xff0c;能够有效提升数据请求与返回的速度&#xff0c;有效应对复杂任务的处理&#xff0c;是提升工作效率的关键。 由于SQL Servers数据库管理系统…

【秋招笔试-支持在线评测】8.28华为秋招(已改编)-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 华为专栏传送🚪 -> 🧷华为春秋招笔试 目前今年秋招的笔…

一文彻底搞懂大模型 - OpenAI o1(最强推理模型)

最近这一两周看到不少互联网公司都已经开始秋招提前批面试了。 不同以往的是&#xff0c;当前职场环境已不再是那个双向奔赴时代了。求职者在变多&#xff0c;HC 在变少&#xff0c;岗位要求还更高了。 最近&#xff0c;我们又陆续整理了很多大厂的面试题&#xff0c;帮助一些…