https://leetcode.com/problems/kth-largest-element-in-an-array/description/
215. Kth Largest Element in an Array
給你一個陣列 nums 和一個數字 k 找出 nums 裡面第 k 大的數字。
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
思路：
1.題目說此題不能排序，想要不排序就快速獲得哪個元素最大可以用計數排序法。
2.因為測資範圍為 -10^4~10^4 所以我們只要建立一個大小為 10^4*2 的計數索引
並計數即可。
---------------------------------------------
class Solution {
public int findKthLargest(int[] nums, int k) {
int[] count = new int[20001];
for (int num : nums) {
count[num + 10000]++;
}
int index = count.length - 1;
int res = 0;
for (int i = 0; i < k; i++) {
while (count[index] == 0) {
index--;
}
res = index - 10000;
count[index]--;
}
return res;
}
}
---------------------------------------------
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1692020096.A.DC6.html
※ 編輯: Rushia (122.100.73.13 臺灣), 08/14/2023 21:35:18