数组中第K个最大元素

这道题目我面试的时候，至少遇到过两次，原理都懂，但是面试的时候每次写都能墨迹好久，下面用两种方式解该题（下面的解法leetcode会超时，暂时先不管）
用堆排序解决，需要清楚父节点和左右子节点对应的索引关系，建堆的时候需要保证父节点的value大于两个子节点的value：

class Solution:
    # left = parent*2 + 1, right = parent*2 + 2
    def swap_heap(self,nums,index):
        n = len(nums)
        if index < n:
            parent_value = nums[index]
            left_flag = False
            right_flag = False
            left = index*2 + 1
            if left < n:
                left_flag = True
            right = index*2 + 2
            if right < n:
                right_flag = True
            max_value = max(parent_value, nums[left] if left_flag else parent_value, nums[right] if right_flag else parent_value)
            if left_flag and max_value == nums[left]:
                nums[index] = nums[left]
                nums[left] = parent_value
                self.swap_heap(nums,left)
            elif right_flag and max_value == nums[right]:
                nums[index] = nums[right]
                nums[right] = parent_value
                self.swap_heap(nums,right)
    
    def create_heap(self,nums):
        index = len(nums)-1
        while index >= 0:
            self.swap_heap(nums,index)
            index -=1  
    
    def print_heap(self,nums,k):
        cur_value = -1
        while k >0:
            cur_value = nums[0]
            nums[0] = nums[-1]
            nums = nums[:-1]
            self.swap_heap(nums,0)
            k -= 1
        return cur_value


    def findKthLargest(self, nums: List[int], k: int) -> int:
        self.create_heap(nums)
        return self.print_heap(nums,k)

用快速排序的方法解：

class Solution:

    def partition_func(self,nums):
        target = nums[0]
        i = 1
        j = 0
        while i < len(nums):
            if nums[i] > target:
                j += 1
                temp = nums[j]
                nums[j] = nums[i]
                nums[i] = temp
            i += 1
        nums[0] = nums[j]
        nums[j] = target
        return j

    def findKthLargest(self, nums: List[int], k: int) -> int:
        index = self.partition_func(nums)
        if index + 1 == k:
            return nums[index] 
        if index+1 < k:
            return self.findKthLargest(nums[index+1:],k-index-1)
        else:
            return self.findKthLargest(nums[:index],k)

查找和最小的 K 对数字

理解起来很简单，所有的pair有$len(nums1)*len(nums2)$个，即如下所示：


参考 【宫水三叶】详解「多路归并」&「二分」两种思路, 多路归并技巧总结 🔥🔥🔥

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        ret = []
        flag = False
        # 第一个数组越小，归并的数量越小，时间复杂度越低
        if len(nums1) > len(nums2):
            flag = True
            nums1,nums2 = nums2,nums1
        pq = []
        # 用第一排的数来建堆，如果需要的k个pair小于并列数，取k
        for i in range(min(len(nums1),k)):
            heapq.heappush(pq,(nums1[i] + nums2[0], i, 0))
        while len(ret) < k and pq:
            # 出堆
            _, a, b = heapq.heappop(pq)
            # 保证存放按原始位置
            ret.append([nums2[b], nums1[a]] if flag else [nums1[a], nums2[b]])
            # 进堆
            if b+1 < len(nums2):
                heapq.heappush(pq, (nums1[a] + nums2[b + 1], a, b + 1))
        return ret