【力扣】数组中的第K个最大元素

一、题目描述

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

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

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

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

题目链接:. - 力扣(LeetCode)

 二、解题思路

1、随机选择基准元素

2、根据基准元素将数组分为三部分:[l, left](该部分小于基准元素key)、[left + 1, right - 1](等于基准元素key)、[right, r](大于基准元素key)。

3、计算每部分所包含的元素个数,分别为a 、b = right - left - 1、 c = r - right + 1;

4、分情况讨论:

三、代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length-1, k);
    }
    private int qsort(int[] nums, int l, int r, int k) {
        if(l == r) {
            return nums[l];
        }
        //随机选择基准元素
        int key = nums[new Random().nextInt(r-l+1) + l];
        //根据基准元素将数组划分为三组
        int left = l-1, right = r+1, i = l;
        while(i < right) {
            if(nums[i] < key) {
                swap(nums, ++left, i++);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(nums, --right, i);
            }
        }
        //分情况讨论
        int b = right - left - 1, c = r - right + 1;
        if(c >= k) {
            return qsort(nums, right, r, k);
        } else if(b + c >= k) {
            return key;
        } else {
            return qsort(nums, l, left, k - b - c);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

 

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

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

相关文章

记一次EasyExcel的错误使用导致的频繁FullGC

记一次EasyExcel的错误使用导致的频繁FullGC 一、背景描述二、场景复现三、原因分析四、解决方案五、思考复盘 一、背景描述 繁忙的校招结束了&#xff0c;美好的大学四年也结束了&#xff0c;作者也有10个月没有更新了。拿到心仪的offer之后也开始了苦B的打工生活。 最近接到…

汽车信息安全--欧盟汽车法规

目录 General regulation 信息安全法规 R155《网络安全及网络安全管理系统》解析 R156《软件升级与软件升级管理系统》解析 General regulation 欧洲的汽车行业受到一系列法律法规的约束&#xff0c;包括 各个方面包括&#xff1a; 1.安全要求&#xff1a;《通用安全条例&a…

10.x86游戏实战-汇编指令lea

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 工具下载&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1rEEJnt85npn7N38Ai0_F2Q?pwd6tw3 提…

SpringBoot之内容协商

现象演示 假设有一个需求是根据终端的不同&#xff0c;返回不同形式的数据&#xff0c;比如 PC 端需要以 HTML 格式返回数据&#xff0c;APP、小程序端需要以 JSON 格式返回数据。这时我们是 coding 几个相似的接口&#xff1f;还是在一个接口里面做复杂判断处理&#xff1f;两…

测试驱动开发(TDD)方法详解

目录 前言1. 什么是测试驱动开发1.1 TDD的基本原则1.2 TDD的优势 2. 测试驱动开发的流程2.1 编写测试2.2 运行测试2.3 编写实现代码2.4 重构代码 3. 常用工具和框架3.1 单元测试框架3.2 Mock框架3.3 集成工具 4. TDD在实际项目中的应用4.1 应用场景4.2 面临的挑战4.3 最佳实践 …

计算机的错误计算(二十二)

摘要 计算机的错误计算&#xff08;十九&#xff09;展示了计算机的一个错误计算&#xff1a;本应该为 0的算式的结果不为0. 那么&#xff0c;增加计算精度&#xff0c;能确定是0吗&#xff1f;不一定。 计算机的错误计算&#xff08;十九&#xff09;展示了计算机对 的错误计…

liunx清理服务器内存和日志

1、查看服务器磁盘占用情况 # 查看磁盘占用大小 df -h 2、删除data文件夹下面的日志 3、查看每个服务下面的日志输出文件&#xff0c;过大就先停掉服务再删除out文件再重启服务 4、先进入想删除输入日志的服务文件夹下&#xff0c;查看服务进程&#xff0c;杀掉进程&#xff…

代码随想录算法训练营第二天|【数组】209.长度最小的子数组

题目 给定一个含有 n 个正整数的数组和一个正整数 s &#xff0c;找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组&#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0。 示例&#xff1a; 输入&#xff1a;s 7, nums [2,3,1,2,4,3] 输出&#…

FPGA开发笔试1

1. 流程简介 我是两天前有FPGA公司的HR来问我实习的事情&#xff0c;她当时问我距离能不能接受&#xff0c;不过确实距离有点远&#xff08;地铁通勤要将近一个半小时&#xff09;&#xff0c;然后她说给我约个时间&#xff0c;抽空做1个小时的题目&#xff08;线上做&#xf…

使用flask的web网页部署介绍

使用flask的web网页部署介绍 文章目录 前言一、网页介绍二、数据库设计介绍总结 前言 flaskbootstrapjquerymysql搭建三叶青在线识别网站&#xff0c;使用nginxgunicorn将网站部署在腾讯云上&#xff0c;配置SSL证书。网站地址&#xff1a;https://www.whtuu.cn 三叶青图像识…

51单片机(STC8051U34K64)_RA8889_SPI4参考代码(v1.3)

硬件&#xff1a;STC8051U34K64 RA8889开发板&#xff08;硬件跳线变更为SPI-4模式&#xff0c;PS101&#xff0c;R143&#xff0c;R141短接&#xff0c;R142不接&#xff09; STC8051U34K64是STC最新推出来的单片机&#xff0c;主要用于替换传统的8051单片机&#xff0c;与标…

【计算机网络】物理层(作业)

1、若信道在无噪声情况下的极限数据传输速率不小于信噪比为30dB 条件下的极限数据传输速率&#xff0c;则信号状态数至少是&#xff08;D&#xff09;。 A. 4B. 16C. 8D. 32 解析&#xff1a;可用奈奎斯特采样定理计算无噪声情况下的极限数据传输速率&#xff0c;用香农第二定…

Qt篇——让子部件忽略父部件的样式表

举例&#xff1a;有一个QGroupBox父部件&#xff0c;在布局中添加了样式QGroupBox{......}&#xff0c;它的有一个子部件QGroupBox&#xff0c;也会沿用父部件的样式。 其实在布局中给父部件添加了样式之后&#xff0c;没有直接让子部件忽略父部件的样式的方法&#xff0c;但是…

SQL Server 2022数据库对象

《SQL Server 2022从入门到精通&#xff08;视频教学超值版&#xff09;》图书介绍-CSDN博客 数据库对象是数据库的组成部分&#xff0c;数据表、视图、索引、存储过程以及触发器等都是数据库对象。 &#xff08;1&#xff09;数据库的主要对象是数据表&#xff0c;数据表是一…

JavaDS预备知识

集合框架 Java 集合框架 Java Collection Framework &#xff0c;又被称为容器 container &#xff0c;是定义在 java.util 包下的一组接口 interfaces和其实现类 classes 。 其主要表现为将多个元素 element 置于一个单元中&#xff0c;对数据进行创建(Create)、读取(Retrieve…

【Vue报错】v-bind动态绑定src无效

今天遇到v-bind动态绑定video的src&#xff0c;出现无效的问题 但是翻看以前的项目都是没问题的 之前的项目 现在的项目 发现并不能呈现视频效果 进行了改进&#xff0c;成功展示

go语言Gin框架的学习路线(六)

gin的路由器 Gin 是一个用 Go (Golang) 编写的 Web 框架&#xff0c;以其高性能和快速路由能力而闻名。在 Gin 中&#xff0c;路由器是框架的核心组件之一&#xff0c;负责处理 HTTP 请求并将其映射到相应的处理函数上。 以下是 Gin 路由器的一些关键特性和工作原理的简要解释…

【前端项目笔记】9 数据报表

数据报表 效果展示&#xff1a; 在开发代码之前新建分支 git checkout -b report 新建分支report git branch 查看分支 git push -u origin report 将本地report分支推送到云端origin并命名为report 通过路由的形式将数据报表加载到页面中 渲染数据报表基本布局 面包屑导航…

[TensorFlow-Lite][深度学习]【快速简介-1】

前言&#xff1a; 很多场景下面我们需要需要把我们的深度学习模型部署到Android,IOS 手机上面. Google 通过TensorFlow Lite 提供了对应的解决方案. 目录&#xff1a; 端侧部署优点 硬件支持 性能 应用案例 一 端侧部署优点 1; 很多场景下面&#xff1a; 无网络,数据无法…

昇思第10天

RNN实现情感分类 二分类问题&#xff1a;Positive和Negative两类 步骤&#xff1a; 1.加载IMDB数据集 2.加载预训练词向量:预训练词向量是对输入单词的数值化表示&#xff0c;通过nn.Embedding层&#xff0c;采用查表的方式&#xff0c;输入单词对应词表中的index&#xff0c;…