代码视界

Hanpeng Chen的个人博客

LeetCode题解|215.数组中的第K个最大元素

本文于 593 天之前发表,文中内容可能已经过时。

前言

前面我们一起学过十种常见的排序算法,我们一起来看一道和排序有关的LeetCode题目:215.数组中的第K个最大元素,题目链接:https://leetcode-cn.com/problems/kth-largest-element-in-an-array/。

题目描述

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

示例 1:

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

解法1:Array.sort()

求解Kth Element问题,我们可以利用Array.sort()方法对数组进行升序排序,然后返回倒数第k个元素即可。

实现代码如下:

1
2
3
4
5
6
7
8
9
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
nums = nums.sort((a, b) => a - b);
return nums[nums.length - k];
};

注意:sort方法如果没有指定排序函数的话,元素按照转换为的字符串的各个字符的Unicode位点进行排序。

解法2:堆排序

堆排序可以用于求解TopK Element问题,也就是K个最小元素的问题。可以维护一个大小为K的最小堆,最小堆中的元素就是最小元素。最小堆需要使用大顶堆来实现,大顶堆表示堆顶元素是堆中最大元素。这是因为我们要得到 k 个最小的元素,因此当遍历到一个新的元素时,需要知道这个新元素是否比堆中最大的元素更小,更小的话就把堆中最大元素去除,并将新元素添加到堆中。所以我们需要很容易得到最大元素并移除最大元素,大顶堆就能很好满足这个要求。

堆也可以用于求解 Kth Element 问题,得到了大小为 k 的最小堆之后,因为使用了大顶堆来实现,因此堆顶元素就是第 k 大的元素。

我们来看下这道题用堆排序的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
let findKthLargest = function(nums, k) {
// 从nums中取出前k个数,构建一个小顶堆
let heap = [,], i = 0
while (i < k) {
heap.push(nums[i++])
}
buildHeap(heap, k)

// 从k位开始遍历数组
for (let i = k; i < nums.length; i++) {
if (heap[1] < nums[i]) {
// 替换并堆化
heap[1] = nums[i]
heapify(heap, k, 1)
}
}
return heap[1]
}

// 原地建堆,从后往前,自上而下式建小顶堆
let buildHeap = function (arr, k) {
if (k === 1) return
// 从最后一个非叶子节点开始,自上而下式堆化
for (let i = Math.floor(k / 2); i >= 1; i--) {
heapify(arr, k, i)
}
}

// 堆化
let heapify = function (arr, k, i) {
while (true) {
let minIndex = i
if (2 * i <= k && arr[2 * i] < arr[i]) {
minIndex = 2 * i
}
if (2 * i + 1 <= k && arr[2 * i +1] < arr[minIndex]) {
minIndex = 2 * i + 1
}
if (minIndex !== i) {
swap(arr, i, minIndex)
i = minIndex
} else {
break
}
}
}

// 交换
let swap = (arr, i , j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}

复杂度分析:

  • 时间复杂度:O(NlogK)
  • 空间复杂度:O(K)

解法3:快速排序

快速排序可以用于求解Kth Element问题,也就是第K个元素的问题。

快速排序也可以求解TopK Element问题,因为找到Kth Element之后,再遍历一次数组,所有小于等于Kth Element的元素都是TopK Elements。

我们来看下使用快速排序解决这道题的实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
let findKthLargest = function(nums, k) {
return quickSelect(nums, nums.length - k)
};

let quickSelect = (arr, k) => {
return quick(arr, 0 , arr.length - 1, k)
}

let quick = (arr, left, right, k) => {
let index
if(left < right) {
// 划分数组
index = partition(arr, left, right)
// Top k
if(k === index) {
return arr[index]
} else if(k < index) {
// Top k 在左边
return quick(arr, left, index-1, k)
} else {
// Top k 在右边
return quick(arr, index+1, right, k)
}
}
return arr[left]
}

let partition = (arr, left, right) => {
// 取中间项为基准
var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
i = left,
j = right
// 开始调整
while(i < j) {

// 左指针右移
while(arr[i] < datum) {
i++
}

// 右指针左移
while(arr[j] > datum) {
j--
}

// 交换
if(i < j) swap(arr, i, j)

// 当数组中存在重复数据时,即都为datum,但位置不同
// 继续递增i,防止死循环
if(arr[i] === arr[j] && i !== j) {
i++
}
}
return i
}

// 交换
let swap = (arr, i , j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}

复杂度分析:

  • 时间复杂度:O(N)
  • 空间复杂度:O(1)
欢迎关注微信公众号: 『前端极客技术』『代码视界』
支付宝打赏 微信打赏

赞赏是不耍流氓的鼓励