Description
給定一個字串陣列
nums，其中每個字串代表一個不含前導零的整數。回傳第 k 大的整數（字串形式）。注意：重複的數字要分開計算。
Example:
Input: nums = [“3”,“6”,“7”,“10”], k = 4 Output: “3”
Intuition#
核心思路：用自訂比較器的 Min Heap（大小為 k）處理大數字串比較，堆頂即為第 k 大。
- 數字以字串表示，可能超過 Long 範圍，需要自訂比較器
- 字串數字比較：先比長度，長度相同再按字典序
- Top-K 問題的標準 Min Heap 解法
Approaches#
1: Sorting#
- 概念: 用自訂比較器排序，直接取第 k 大
- 時間複雜度:
O(n log n * L)- L 為字串平均長度 - 空間複雜度:
O(n)
class Solution {
fun kthLargestNumber(nums: Array<String>, k: Int): String {
nums.sortWith(Comparator { a, b ->
if (a.length != b.length) a.length - b.length
else a.compareTo(b)
})
return nums[nums.size - k]
}
}⭐2: Min Heap#
- 概念: 用大小為 k 的 Min Heap，自訂字串數字比較器，堆頂即為第 k 大
- 時間複雜度:
O(n log k * L)- L 為字串平均長度 - 空間複雜度:
O(k)
class Solution {
fun kthLargestNumber(nums: Array<String>, k: Int): String {
val minHeap = PriorityQueue<String>(Comparator { a, b ->
if (a.length != b.length) a.length - b.length
else a.compareTo(b)
})
for (num in nums) {
minHeap.offer(num)
if (minHeap.size > k) {
minHeap.poll()
}
}
return minHeap.peek()
}
}🔑 Takeaways#
- Pattern: Top-K 問題 → 大小為 k 的 Min Heap，堆頂為答案
- 關鍵技巧: 大數字串比較先比長度再比字典序；此題是 215. Kth Largest Element 的字串版本