找第k小及变种

常见思路

1. 对结果二分查找
   1. 需要看判定复杂度是多少，考虑下有序后再遍历，o(n)是否判定。
2. max heap大顶堆.
   1. 对于找前k小是否有效
   2. heap大小维护在不超过k，超过则弹出堆顶
3. 多路链表归并
   1. 看能否抽象成多路链表归并
   2. 可以用heap取最小值优化成每次取最小链路时时间复杂度是o(logn)。总的是O(klogn)

应用

719. 找出第 k 小的距离对 给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

• [preferred]对结果二分解法 o(nlogn) 先排序后再每次判定就可以o(n)判定了，其实就是有序数组的滑动窗口，当slow不符合条件时slow+=1

• 多路链表归并 o(klogn) 排序然后类似超级丑数，对每个item维护右边指针，每次取最小，然后右移指针，总共k次。k最大接近n^2

• 大顶堆，o(n2logk) 找到所有距离对o(n2)，不断插入大顶堆，维护长度不超过k.

378. 有序矩阵中第 K 小的元素 给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

• [preferred]对结果二分 判定可以o(m+n)时间复杂度： 从bottom-left 开始，维护(i,j)，每次i-=1时，不断增加j, w+=j, 累积和和mid比较

• class Solution:
      def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
          n = len(matrix)
    
          def check(mid):
              i, j = n - 1, 0
              num = 0
              while i >= 0 and j < n:
                  if matrix[i][j] <= mid:
                      num += i + 1
                      j += 1
                  else:
                      i -= 1
              return num >= k
    
          left, right = matrix[0][0], matrix[-1][-1]
          while left < right:
              mid = (left + right) // 2
              if check(mid):
                  right = mid
              else:
                  left = mid + 1
            
          return left
  

• 多路链表归并 对每行维护列指针…

• 大顶堆 ….

313. 超级丑数 和 剑指 Offer 49. 丑数 超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

• 多路归并 其实就是2一个链路、3一个链路、5一个链路，然后归并

  「往后产生的丑数」都是基于「已有丑数」而来（使用「已有丑数」乘上「给定质因数」primes[i]）。

下面时间复杂度是o(klog(n)) n是数组长度

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        import heapq
        hpush, hpop = heapq.heappush,heapq.heappop
        h = []
        for i in range(len(primes)):
            hpush(h, (primes[i], i, 0))
        ans = [1]
        for i in range(1,n):
            if not h:
                return -1
            val = h[0][0]
            ans.append(val)
            while h and h[0][0] == val:
                _,j,idx = hpop(h)
                # print(idx,ans)
                hpush(h, (ans[idx]*primes[j], j, idx+1))
        return ans[-1]
            

下面这个时间复杂度不对，是o(nklog(n)) 不应该是下面这种写法。

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        import heapq
        hq = [1]
        res = []
        for _ in range(n):
            top = heapq.heappop(hq)
            res.append(top)
            while hq and hq[0] == top:
                heapq.heappop(hq)
            for k in primes:
                heapq.heappush(hq, top * k)
        print(res)
        return res[-1]

使用多指针。 它没有用堆来优化，时间复杂度O(klog(n))

//cpp:
class Solution {
public:/
    int GetUglyNumber_Solution(int index) {
        if (index < 7)return index;
        vector<int> res(index);
        res[0] = 1;
        int t2 = 0, t3 = 0, t5 = 0, i;
        for (i = 1; i < index; ++i)
        {
            res[i] = min(res[t2] * 2, min(res[t3] * 3, res[t5] * 5));
            if (res[i] == res[t2] * 2)t2++;
            if (res[i] == res[t3] * 3)t3++;
            if (res[i] == res[t5] * 5)t5++;
        }
        return res[index - 1];
    }
};

• 373. 查找和最小的K对数字 给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。请找到和最小的 k 个数对 (u1,v1), ` (u2,v2) ... (uk,vk)` 。

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        # equal with 多路链表归并，用heap取最小那个,然后移动指针，也就是超级丑数
        # 性能o(klog(k))
        import heapq
        h = []
        for j in range(min(len(nums2),k)):
            heapq.heappush(h, (nums1[0]+nums2[j], 0, j))
        res = []
        while k > 0 and h:
            _,i,j = heapq.heappop(h)
            res.append([nums1[i], nums2[j]])
            if i+1 < len(nums1):
                heapq.heappush(h, (nums1[i+1]+nums2[j], i+1,j))
            k-=1
        return res