題目描述:
給定一個字串陣列 nums,其中每個字串代表一個正整數(不含前導零),以及整數 k。回傳第 k 大的整數對應的字串。注意,相同數值的重複字串各自獨立計算排名。
解題思路: 由於數字可能非常大(超出 64 位整數範圍),不能直接轉為整數比較。需要自定義字串比較函式:
使用此比較函式排序後,取第 k 個即可。也可以用 nth_element 做部分排序以獲得 O(n) 平均時間。
時間複雜度: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 的情況。