牛客-寻找第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+1
        while (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大,那么从小到大的顺序就是k
        return 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

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

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

相关文章

pytest -- 进阶使用详解

pytest-html⽣成报告 Pytest-HTML 是⼀个插件&#xff0c;它可以⽣成漂亮且易于阅读的 HTML 测试报告。 pytest-html ⽣成报告的步骤 ① 安装 pytest-html 插件&#xff1a; pip install pytest-html ② 运⾏测试并⽣成报告&#xff1a; file name:main.pyimport pytest&qu…

苹果MAC怎么清理内存?苹果MAC清理内存的方法

很多使用苹果电脑的用户都喜欢在同时运行多个软件&#xff0c;不过这样会导致在运行一些大型软件的时候出现不必要的卡顿现象&#xff0c;这时候我们就可以去清理下内存&#xff0c;不过很多人可能并不知道正确的清内存方式&#xff0c;下面就和小编一起来看看吧。 苹果MAC清理…

opengauss-高斯数据库的安装部署及MySQL数据迁移实战.

目录 介绍 下载安装包 安装 1.设置SEMMNI 2.新建用户和用户组 3.下载安装包解压 4.安装数据库 5.修改配置 6.重启服务 数据库使用 gsql命令和常用sql 1.使用omm用户连接数据库-本地登陆无需输入密码&#xff1a; 2.查看用户信息 3.删除数据库 4.创建用户 5.创建…

SSL之mkcert构建本地自签名

文章目录 1. 什么是SSL2. mkcert&#xff1a;快速生成自签名证书2.1 mkcert的工作流程如下&#xff1a;2.2 window 本地实现自签证书2.2.1 下载安装2.2.2 下载,生成本地 SSL2.2.3 生成 pem 自签证书,可供局域网内使用其他主机访问。2.2.4 使用-psck12 生成*.p12 文件 2.3 Sprin…

【设计模式-06】Observer观察者模式

简要说明 事件处理模型 场景示例&#xff1a;小朋友睡醒了哭&#xff0c;饿&#xff01; 一、v1版本(披着面向对象的外衣的面向过程) /*** description: 观察者模式-v1版本(披着面向对象的外衣的面向过程)* author: flygo* time: 2022/7/18 16:57*/ public class ObserverMain…

Odoo14 动态过滤或联动domain

在 Odoo14 中最常用的动态过滤或联动domain的方法有两种 1. 使用 上下文 context 和 重写 _search() 或 _name_search() 方法 2. 使用 onchange() 装饰器 的 domain 返回值 示例&#xff1a; 这个图有字段&#xff1a;项目&#xff0c;上级任务&#xff0c;任务 要求&#…

论文笔记(四十)Goal-Auxiliary Actor-Critic for 6D Robotic Grasping with Point Clouds

Goal-Auxiliary Actor-Critic for 6D Robotic Grasping with Point Clouds 文章概括摘要1. 介绍2. 相关工作3. 学习 6D 抓握政策3.1 背景3.2 从点云抓取 6D 策略3.3 联合运动和抓握规划器的演示3.4 行为克隆和 DAGGER3.5 目标--辅助 DDPG3.6 对未知物体进行微调的后视目标 4. 实…

现代密码学 考点汇总(上)

现代密码学 考点汇总&#xff08;上&#xff09; 写在最前面考试范围一、给一个简单的方案&#xff0c;判断是否cca安全二、随机预言机模型之下的简单应用 0. 规约证明一个规约法证明PRG&#xff08;伪随机生成器&#xff09;的例子定长加密方案&#xff0c;并证明不可区分加密…

【二、自动化测试】为什么要做自动化测试?哪种项目适合做自动化?

自动化测试是一种软件测试方法&#xff0c;通过编写和使用自动化脚本和工具&#xff0c;以自动执行测试用例并生成结果。 自动化旨在替代手动测试过程&#xff0c;提高测试效率和准确性。 自动化测试可以覆盖多种测试类型&#xff0c;包括功能测试、性能测试、安全测试等&…

wins安装paddle框架

一、安装 https://www.paddlepaddle.org.cn/install/quick?docurl/documentation/docs/zh/install/pip/windows-pip.html 装包&#xff08;python 的版本是否满足要求&#xff1a; 3.8/3.9/3.10/3.11/3.12&#xff0c; pip 版本为 20.2.2 或更高版本 &#xff09; CPU 版:…

python贪吃蛇游戏

为了实现这个游戏&#xff0c;需要用到Python的pygame模块&#xff0c;它是一个专门用于开发游戏的模块&#xff0c;提供了很多方便的功能&#xff0c;比如窗口、图形、音效、事件处理等。 用pygame来创建一个窗口&#xff0c;设置游戏的背景色&#xff0c;画出蛇和食物&#…

Flutter首页框架搭建

1.下载flutter 2. 安装android 3.配置环境变量 关于环境搭建部分&#xff0c;哪天写一下&#xff0c;日志杂乱无章。 打开android studio 新建项目&#xff0c;选择flutter 新建文件夹创建 navigator和pages 文件夹下分别创建文件&#xff0c;tab_navigator.dart&#xff…

Docker RTMP服务器搭建与视频流推送示例(流媒体服务器tiangolo/nginx-rtmp,推流客户端ffmpeg)

文章目录 RTMP服务器搭建与视频流推送第一部分&#xff1a;搭建RTMP服务器&#xff08;流媒体服务器&#xff09;1.1 安装Docker1.2 搭建RTMP服务器 第二部分&#xff1a;使用ffmpeg进行视频推流&#xff08;推流客户端&#xff09;2.1 安装ffmpeg2.2 使用ffmpeg推流 第三部分&…

【数据结构】二叉树-堆(top-k问题,堆排序,时间复杂度)

&#x1f308;个人主页&#xff1a;秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343&#x1f525; 系列专栏&#xff1a;《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm1001.2014.3001.5482 ​​ 目录 堆排序 第一种 ​编辑 第二种 …

npm install 无反应 npm run serve 无反应

说明情况&#xff1a;其实最开始我就是发现我跟着黑马的苍穹外卖的前端day2的环境搭建做的时候&#xff0c;到这一步出现了问题&#xff0c;无论我怎么 npm install 和 npm run serve 都没有像黑马一样有很多东西进行加载&#xff0c;因此我换了一种方法 1.在这个文件夹下cmd …

助力工业焊缝质量检测,YOLOv3开发构建工业焊接场景下钢材管道焊缝质量检测识别分析系统

焊接是一个不陌生但是对于开发来说相对小众的场景&#xff0c;在我们前面的博文开发实践中也有一些相关的实践&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 《轻量级模型YOLOv5-Lite基于自己的数据集【焊接质量检测】从零构建模型超详细教程》 《基于DeepLabV3Pl…

计算机组成原理-程序中断方式完整流程

文章目录 程序中断方式完整流程例题小结 程序中断方式完整流程 首先CPU通过执行IO指令来启动外部设备&#xff0c;此时外部设备可以开始做准备工作了&#xff08;准备CPU想要的数据或者信息&#xff09;&#xff0c;在外部设备准备过程中&#xff0c;CPU可以继续执行原程序的内…

CES 2024,从枕头到汽车,一切皆可AI

文 / 胡泳 北京大学新闻与传播学院教授 世界上最大的消费类电子展CES是令人难以置信的创新的展示舞台。 我在拉斯维加斯泡了四五天&#xff0c;跟踪了展出的大部分小工具、应用程序和概念产品。这些产品既有趣又实用&#xff0c;它们要么以全新的方式利用技术解决了某个特定的问…

AI对决:ChatGPT与文心一言的比较

. 个人主页&#xff1a;晓风飞 专栏&#xff1a;数据结构|Linux|C语言 路漫漫其修远兮&#xff0c;吾将上下而求索 文章目录 引言ChatGPT与文心一言的比较Chatgpt的看法文心一言的看法Copilot的观点chatgpt4.0的回答 模型的自我评价自我评价 ChatGPT的优势在这里插入图片描述 文…

JS-var 、let 、 const使用介绍

变量声明介绍 在我们日常开发用&#xff0c;变量声明有三个 var、 let 和 const&#xff0c;我们应该用那个呢&#xff1f; 首先var 先排除&#xff0c;老派写法&#xff0c;问题很多&#xff0c;可以淘汰掉…let or const ?建议&#xff1a; const 优先&#xff0c;尽量使…