MediumRating 1414
1985. Find the Kth Largest Integer in the Array
arraystringdivide-and-conquersortingheap-priority-queuequickselect
解題說明
Find the Kth Largest Integer in the Array
題目描述：
給定一個字串陣列 nums，其中每個字串代表一個正整數（不含前導零），以及整數 k。回傳第 k 大的整數對應的字串。注意，相同數值的重複字串各自獨立計算排名。
解題思路： 由於數字可能非常大（超出 64 位整數範圍），不能直接轉為整數比較。需要自定義字串比較函式：
- 先比較長度：較長的字串代表更大的數。
- 長度相同時，直接按字典序比較。
使用此比較函式排序後，取第 k 個即可。也可以用 nth_element 做部分排序以獲得 O(n) 平均時間。
C++ 解法
複雜度分析
時間複雜度：O(n * m * log n) — 排序需要 O(n log n) 次比較，每次比較字串最長 O(m)（m 為字串最大長度）。
空間複雜度：O(m * log n) — 排序的遞迴堆疊空間，每層涉及 O(m) 的字串比較。
虛擬碼
1. Define comparator: compare two number strings a, b a. If lengths differ: longer string is larger b. If lengths equal: lexicographically larger string is larger 2. Sort nums in descending order using comparator 3. Return nums[k-1]
其他解法
nth_element 部分排序 O(n * m)：使用 nth_element 找到第 k 大的元素，平均時間複雜度更優。但最壞情況仍為 O(n^2 * m)。
最小堆 O(n * m * log k)：維護大小為 k 的最小堆，遍歷完成後堆頂即為答案。適合 k 遠小於 n 的情況。
延伸思考
- 如果數字可能包含前導零，比較函式需要如何修改？
- 如何處理第 k 大元素有重複的情況？（例如需要去重後排名）
- 此題能否用基數排序（Radix Sort）在 O(n * m) 時間內解決？