当前位置： 面试刷题>> n数组第k大元素 (经典算法题500道)

题目描述补充

题目：给定一个整数数组 nums 和一个整数 k，找出并返回该数组中的第 k 大元素。请注意，数组中的元素可能不是唯一的，且 k 的取值范围是 [1, 数组长度]。

示例

示例 1:

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

示例 2:

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

解题思路

  1. 排序法：直接对数组进行排序，然后返回第 n-k+1 个元素（数组索引从0开始）。
  2. 快速选择法：利用快速排序的分区思想，每次分区后判断分区元素的位置与 k 的关系，然后继续在左边或右边递归查找。

示例代码

PHP 示例代码

function findKthLargest($nums, $k) {
    rsort($nums); // 降序排序
    return $nums[$k - 1]; // 数组索引从0开始，所以返回第k-1个元素
}

// 使用示例
$nums = [3,2,1,5,6,4];
$k = 2;
echo findKthLargest($nums, $k); // 输出 5

注意：PHP 示例中使用了 rsort() 函数进行降序排序，因为题目要求第 k 大元素。

Python 示例代码

def findKthLargest(nums, k):
    nums.sort(reverse=True) # 降序排序
    return nums[k-1] # 返回第k大元素

# 使用示例
nums = [3,2,1,5,6,4]
k = 2
print(findKthLargest(nums, k)) # 输出 5

JavaScript 示例代码

function findKthLargest(nums, k) {
    nums.sort((a, b) => b - a); // 降序排序
    return nums[k - 1]; // 返回第k大元素
}

// 使用示例
const nums = [3,2,1,5,6,4];
const k = 2;
console.log(findKthLargest(nums, k)); // 输出 5

码小课

码小课网站中有更多关于算法和数据结构的深入内容分享，包括快速选择算法、堆排序等高级话题，可以帮助你更好地理解和解决这类问题。建议深入学习和实践，以提升自己的编程技能。

推荐面试题