【刷题第四天】剑指 Offer II 076. 数组中的第 k 大的数字

作者：白日梦

2022 年 5 月 10 日
本文字数：1131 字
阅读完需：约 4 分钟

一、题目描述：

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

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

示例

示例 1:

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

示例 2:

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

二、思路分析：

使用 sort 函数

首先声明这个题我不能接受，能使用 api 离谱大了，也怪我脑子转的太慢了，光考虑到快速排序方法了，却未曾想 sort 排序，我服了。虽然这种方法又简单又暴力，但不推荐使用，还是按部就班的使用快速排序的方式，还能锻炼自己。

var findKthLargest = function(nums, k) {    nums.sort((v1,v2)=>v1-v2)    console.log(nums)    return nums[nums.length-k]};

复制代码

冒泡排序

我们大一时在学习基础算法时，曾经学过简单的几种排序方式，例如插入排序、选择排序、冒牌排序。

冒泡排序每一轮可以选出一个最值，那么我们可以利用这个机制，冒泡 k 轮即可。代码比较简单，这里就不实现了。

冒泡排序时间复杂度为 O(n2)

基于快速排序的选择方法

我们回忆一下快速排序的流程，快速排序是一个标准的分治算法。

分解：我们选择一个基准，例如左端点为基准，然后对数组进行划分，一侧比基准大，一侧比基准小，划分完成后将基准填入对应位置(因为左边的一定比基准小，右边的一定比基准大，那是不是就是说，基准的定位是准确的，我们就可以根据这个特性来求解第 k 大的元素)
递归: 递归调用快速排序，分别对左侧和右侧进行排序
合并: 递归过程中已经排序完毕，因此无需合并过程

因此我们就可以通过比较基准与 k 的大小，如果相等，则寻找成功，不相等，根据情况递归即可。

三、AC 代码：

var partition = function (nums, l, r) {    let i = l, j = r;    let base = nums[l];    while (i < j) {        while (nums[j] >= base && j > i) j --;        nums[i] = nums[j];        while (nums[i] < base && i < j) i ++;        nums[j] = nums[i]    }    nums[i] = base;    return i;}var sort = function (nums, i, j, kMax) {    if (i <= j) {        const part = partition(nums, i, j);        console.log(part,kMax)        if (part == kMax) {            return nums[part]        }else if (part > kMax) {            return sort(nums, i, part - 1, kMax);        }else {            return sort(nums, part + 1, j, kMax)        }     }}var findKthLargest = function(nums, k) {    const kMax = nums.length - k;    return sort(nums, 0, nums.length - 1, kMax)};

复制代码

四、总结：

通过训练本题目，不止成功的 AC ，还重新复习了快速排序，但并非是最快的，如果没记错，sort 方法基于的堆排序非常适合于求解第 k 个 xx 元素。

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/34af531d616b85526755fbb5a】。文章转载请联系作者。

白日梦

关注

还未添加个人签名 2022.03.10 加入

还未添加个人简介

发布

暂无评论

创作场景