215. Kth Largest Element in an Array

215. Kth Largest Element in an Arrayopen in new window

🟠 🔖 数组 分治 快速选择 排序 堆（优先队列） 🔗 LeetCodeopen in new window

题目

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

题目大意

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

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

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

解题思路

思路一：快速选择算法

每次选取一个基准元素（类似于快速排序中的划分操作），将数组划分为两部分，然后根据基准元素的位置来确定下一步是在左侧还是右侧进行查找。这样，每次划分都能将问题规模缩小一半。

选择数组中的一个元素作为基准元素（可以随机选择）。
根据基准元素将数组划分为两部分，左侧部分的元素大于等于基准元素，右侧部分的元素小于基准元素。
如果基准元素的位置等于 k，则找到了第 k 个最大的元素；
如果基准元素的位置小于 k，则在右侧部分递归查找；
如果基准元素的位置大于 k，则在左侧部分递归查找；

平均情况下的时间复杂度为 O(n) 。

思路二：小顶堆

针对静态数据，想要在一个包含 n 个数据的数组中，查找前 K 大的数据，可以维护一个大小为 K 的小顶堆：

顺序遍历数组，从数组中取出取数据与堆顶元素比较；
如果比堆顶元素大，就把堆顶元素删除，并且将这个元素插入到堆中；
如果比堆顶元素小，则不做处理，继续遍历数组；
遍历完数组中的数据之后，堆顶元素就是第 K 大的数

遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，所以时间复杂度就是 O(nlogK) 。

代码

快速选择算法

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
	const quickSelect = (left, right) => {
		const index = partition(left, right);
		if (index == k - 1) {
			return nums[index];
		} else if (index > k - 1) {
			return quickSelect(left, index - 1);
		} else {
			return quickSelect(index + 1, right);
		}
	};
	const partition = (left, right) => {
		const pivot = nums[right];
		let i = left;
		for (let j = left; j < right; j++) {
			if (nums[j] > pivot) {
				[nums[i], nums[j]] = [nums[j], nums[i]];
				i++;
			}
		}
		[nums[i], nums[right]] = [nums[right], nums[i]];
		return i;
	};
	return quickSelect(0, nums.length - 1);
};

小顶堆

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
	let heap = [];
	const add = (val) => {
		if (heap.length < k) {
			heap.push(val);
			heapifyUp(heap.length - 1);
		} else if (val > heap[0]) {
			heap[0] = val;
			heapifyDown(0);
		}
	};
	const heapifyUp = (i) => {
		while (i > 0) {
			const parent = Math.floor((i - 1) / 2);
			if (heap[parent] > heap[i]) {
				[heap[parent], heap[i]] = [heap[i], heap[parent]];
				i = parent;
			} else {
				break;
			}
		}
	};
	const heapifyDown = (i) => {
		const left = i * 2 + 1;
		const right = i * 2 + 2;
		let min = i;
		if (left < heap.length && heap[left] < heap[min]) {
			min = left;
		}
		if (right < heap.length && heap[right] < heap[min]) {
			min = right;
		}
		if (min !== i) {
			[heap[min], heap[i]] = [heap[i], heap[min]];
			heapifyDown(min);
		}
	};
	for (let i of nums) {
		add(i);
	}
	return heap[0];
};

215. Kth Largest Element in an Array

# 215. Kth Largest Element in an Arrayopen in new window

# 题目

# 题目大意

# 解题思路

# 思路一：快速选择算法

# 思路二：小顶堆

# 代码

# 相关题目

215. Kth Largest Element in an Arrayopen in new window

题目

题目大意

解题思路

思路一：快速选择算法

思路二：小顶堆

代码

相关题目