基本信息

  • 题号：1985
  • 题厂：谷歌、脸书、亚麻
  • 难度系数：中


有一个数组，找到排行 k 的整数，并返回

例如：nums = ["3","6","7","10"], k = 4 

第 4 大的是 3，返回 3（当然这里需要做字符与整数之间数据类型转换）


解题思路

  • 寻找 K 。。。的元素，一般需要 heap 登场
  • 如果本题能想到运用 heap（priority queue），剩下的逻辑还是很简单的
class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        # 初始化 minHeap
        minHeap = []
        heapq.heapify(minHeap)
        
        for n in nums:
            # 如果 minHeap 的长度小于 k，说明还可以往里面塞;
            # 如果 minHeap 长度等于 k，考察当前元素 与 minHeap 最小值——如果当前元素大于 minHeap 最小值，说明可以替换……
            if len(minHeap) < k:
                heapq.heappush(minHeap, int(n))
            elif int(n) > curMin:
                heapq.heappop(minHeap)
                heapq.heappush(minHeap, int(n))
        
        # 遍历结束后，返回 minHeap 第一个元素，即最小值          
        return str(heapq.heappop(minHeap))


Constraints

  • 1 <= k <= nums.length <= 104
  • 1 <= nums[i].length <= 100
  • nums[i] consists of only digits.
  • nums[i] will not have any leading zeros.

解题前，可以就 k 和 nums 数组长度取值范围，与考官进行讨论并确认

另外本题涉及字符和整数之间转换问题，也需要就此进行确认……


Big O

  • Time：O（ n * logn ）做了一遍循环 O（n），每次遍历时 minHeap 需要整理一次 O（logn）
  • Space：O（n）


当然本题既然可以用 minHeap 做，稍微反一下，用 maxHeap 也一样可以反向操作，原理都是利用 heap；

而此时的big O 为 O（n + klogn），考虑到 k 有很大的情况

class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        maxHeap = [-int(n) for n in nums ]
        heapq.heapify(maxHeap)
        
        # 当 k 大于 1 时，就不停 pop；
        # 最后那个留给返回 🙈
        while k > 1:
            heapq.heappop(maxHeap)
            k -= 1
        
        return str(-heapq.heappop(maxHeap))


不过，貌似无论 minHeap 还是 maxHeap，效率半斤八两😅



测试

  • 当 nums 为 1 时
  • 当 nums 有元素重复时
  • ……


总结

  • 不熟悉 heap 操作特征是不可能想出解答的，知道用 heap 后其实本题还是很 easy 的
  • 虽然代码简单，但 heap 属于较高级数据结构，所以本题划归中档🥲
  • 本题有多种解题方法，考察了 heap 使用的经典用法——heap 常常用来解决“找第 k 元素”题型
  • 本题需要作为 heap 类别经典面试题型定期复习，熟悉各种解题思路加深对 heap 的认知