给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
以空间换时间，数组下标不能为负数，故下标整体后移10000个单位，结果再返回
class Solution: def findKthLargest(self, nums, k): bucket = [0] * 20005 for n in nums: bucket[n + 10000] += 1 sum_val = 0 for i in range(20004, -1, -1): sum_val += bucket[i] if sum_val >= k: return i - 10000 return 0
- 创建一个长度为 20005 的数组
bucket，用于记录每个元素出现的次数。数组的索引从 -10000 到 10004，对应了可能的元素取值范围。 - 遍历输入数组
nums，将每个元素的出现次数记录在bucket数组中。具体而言，对于元素n，在bucket[n + 10000]的位置加一。 - 从
bucket数组的末尾开始向前遍历，累积每个索引处的元素出现次数（从大到小累积）。当累积次数达到或超过 k 时，返回当前索引值减去 10000，即找到了第 k 大的元素。 - 如果遍历完整个
bucket数组后还没有找到第 k 大的元素，返回默认值 0。
总体来说，该算法使用桶排序的思想，通过统计每个元素的出现次数，从大到小遍历桶来找到第 k 大的元素。
C语言实现
#include <stdio.h> int findKthLargest(int* nums, int size, int k) { int bucket[20005] = {0}; // Count the occurrences of each element in the bucket array. for (int i = 0; i < size; i++) { bucket[nums[i] + 10000]++; } // Traverse the bucket array from the end to find the kth largest element. int sum = 0; for (int i = 20004; i >= 0; i--) { sum += bucket[i]; if (sum >= k) { return i - 10000; } } return 0; } int main() { // Example usage: int nums[] = {3, 1, 4, 4, 2}; int size = sizeof(nums) / sizeof(nums[0]); int k = 2; int result = findKthLargest(nums, size, k); printf("The %dth largest element is: %d\n", k, result); return 0; }
