当前位置： 面试刷题>> 第k大元素 (经典算法题500道)
### 题目描述补充
给定一个未排序的整数数组 `nums` 和一个整数 `k`，找出数组中第 `k` 大的元素。请注意，这里的 `k` 是从 1 开始计数的，即数组中的最大元素是第 1 大的，次大元素是第 2 大的，以此类推。
### 示例
**输入**:
- `nums = [3,2,1,5,6,4]`
- `k = 2`
**输出**:
- `5`
**解释**:
- 数组中的元素排序后为 `[1,2,3,4,5,6]`，第 2 大的元素是 `5`。
### 解题思路
有多种方法可以解决此问题，包括使用最小堆、快速选择算法等。这里将分别给出 PHP、Python 和 JavaScript 的实现示例，使用快速选择算法，因为它在平均情况下具有更好的时间复杂度（O(n)）。
### PHP 示例代码
```php
function findKthLargest($nums, $k) {
$n = count($nums);
$k = $n - $k + 1; // 转换为第 k 小的元素
$left = 0;
$right = $n - 1;
while (true) {
$pivotIndex = partition($nums, $left, $right);
if ($pivotIndex == $k - 1) {
return $nums[$pivotIndex];
} elseif ($pivotIndex < $k - 1) {
$left = $pivotIndex + 1;
} else {
$right = $pivotIndex - 1;
}
}
}
function partition(&$nums, $left, $right) {
$pivot = $nums[$right];
$i = $left - 1;
for ($j = $left; $j < $right; $j++) {
if ($nums[$j] <= $pivot) {
$i++;
// 交换
$temp = $nums[$i];
$nums[$i] = $nums[$j];
$nums[$j] = $temp;
}
}
// 将 pivot 放到中间
$temp = $nums[$i + 1];
$nums[$i + 1] = $nums[$right];
$nums[$right] = $temp;
return $i + 1;
}
// 示例使用
$nums = [3, 2, 1, 5, 6, 4];
$k = 2;
echo findKthLargest($nums, $k); // 输出 5
```
### Python 示例代码
```python
def findKthLargest(nums, k):
def partition(left, right, pivot_index):
pivot_value = nums[pivot_index]
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
store_index = left
for i in range(left, right):
if nums[i] <= pivot_value:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
nums[store_index], nums[right] = nums[right], nums[store_index]
return store_index
left, right = 0, len(nums) - 1
k = len(nums) - k # 转换为第 k 小的元素
while left <= right:
pivot_index = random.randint(left, right) # 随机选择pivot
new_pivot_index = partition(left, right, pivot_index)
if new_pivot_index == k:
return nums[k]
elif new_pivot_index < k:
left = new_pivot_index + 1
else:
right = new_pivot_index - 1
# 示例使用
import random
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(findKthLargest(nums, k)) # 输出 5
```
### JavaScript 示例代码
```javascript
function findKthLargest(nums, k) {
let left = 0;
let right = nums.length - 1;
k = nums.length - k; // 转换为第 k 小的元素
while (true) {
let pivotIndex = partition(nums, left, right);
if (pivotIndex === k) {
return nums[pivotIndex];
} else if (pivotIndex < k) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
}
function partition(nums, left, right) {
let pivot = nums[right];
let i = left - 1;
for (let j = left; j < right; j++) {
if (nums[j] <= pivot) {
i++;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
[nums[i + 1], nums[right]] = [nums[right], nums[i + 1]];
return i + 1;
}
// 示例使用
let nums = [3, 2, 1, 5, 6, 4];
let k = 2;
console.log(findKthLargest(nums, k)); // 输出 5
```
**码小课**：在码小课网站上，你可以找到更多关于算法和数据结构的深入解析和练习，帮助你更好地掌握这些技术。