前言

• 大家好慕购，我是新人簡書博主：「 個(gè)人主頁」主要分享程序員生活拳昌、編程技術(shù)惜犀、以及每日的LeetCode刷題記錄捺氢，歡迎大家關(guān)注我惜姐，一起學(xué)習(xí)交流，謝謝胡岔！
  正在堅(jiān)持每日更新LeetCode每日一題法希，發(fā)布的題解有些會(huì)參考其他大佬的思路(參考資料的鏈接會(huì)放在最下面)，歡迎大家關(guān)注我 ~ ~ ~
  今天是堅(jiān)持寫題解的18天(haha靶瘸，從21年圣誕節(jié)開始的)苫亦，大家一起加油！

• 每日一題：LeetCode：373.查找和最小的K對(duì)數(shù)字

  • 時(shí)間：2022-01-14
  • 力扣難度：Meduim
  • 個(gè)人難度：Meduim
  • 數(shù)據(jù)結(jié)構(gòu)：數(shù)組怨咪、堆屋剑、優(yōu)先隊(duì)列
  • 算法：多路歸并 、二分
  • Tips：本題屬于非常高頻的面試題诗眨，有可能直接手撕唉匾，或者是以考察大文件排序、海量數(shù)據(jù)排序等場景題的方式出現(xiàn)

LeetCode每日一題.jpg

2022-01-14：LeetCode：373.查找和最小的K對(duì)數(shù)字

1. 題目描述

• 題目：原題鏈接

  • 給定兩個(gè)以 升序排列 的整數(shù)數(shù)組 nums1 和 nums2 , 以及一個(gè)整數(shù) k 匠楚。
  • 定義一對(duì)值 (u,v)巍膘，其中第一個(gè)元素來自 nums1，第二個(gè)元素來自 nums2 芋簿。
  • 請(qǐng)找到和最小的 k 個(gè)數(shù)對(duì) (u1,v1), (u2,v2) ... (uk,vk) 峡懈。

• 輸入輸出規(guī)范

  • 輸入：兩個(gè)升序數(shù)組
  • 輸出：K個(gè)數(shù)對(duì)(i, j)

• 輸入輸出示例

  • 輸入：nums1 = [1,7,11], nums2 = [2,4,6], k = 3
  • 輸出：[1,2],[1,4],[1,6]

2. 方法一：多路歸并 & 小根堆

• 思路：優(yōu)先隊(duì)列中維護(hù)K個(gè)數(shù)對(duì)

  • 本題是TopK類型問題，可以參考LC215數(shù)組的第K大個(gè)元素即求出一個(gè)序列中的K大或K小個(gè)元素与斤，與普通的TopK問題不同的是本題是兩個(gè)升序數(shù)組肪康，然后求解的是K小個(gè)數(shù)對(duì)
  • 首先，可以想到最基礎(chǔ)的方法是撩穿，將兩個(gè)數(shù)組可以組成的數(shù)對(duì)全部枚舉出來磷支，并對(duì)這些元素進(jìn)行排序，最終取出K小個(gè)元素對(duì)應(yīng)的數(shù)對(duì)即可冗锁，時(shí)間復(fù)雜度取決于排序算法的復(fù)雜度齐唆，一般為
  • 這種方法屬于暴力枚舉，復(fù)雜度較高冻河，所以需要進(jìn)行優(yōu)化，實(shí)際上茉帅，對(duì)于TopK問題叨叙，我們完全不需要對(duì)整個(gè)序列進(jìn)行排序，而是只關(guān)心TopK個(gè)元素
  • 所以堪澎，我們只需要維護(hù)K個(gè)元素擂错，并取出其中的最值，然后每次添加進(jìn)來一個(gè)新元素樱蛤，繼續(xù)取出最值钮呀，這些最值組成的集合就是最終的TopK個(gè)元素
  • 這種思想類似于堆結(jié)構(gòu)剑鞍，即大根堆和小根堆，Java中提供了基于堆思想的PriorityQueue優(yōu)先隊(duì)列結(jié)構(gòu)爽醋，無需我們手動(dòng)構(gòu)建堆

• 堆的常規(guī)解題方式：以K小為例

  • 方式一：結(jié)果為堆中元素
    • 對(duì)于單個(gè)序列的TopK問題蚁署，首先將序列的前 k 個(gè)元素添加到大根堆(降序)中
    • 然后遍歷剩下的 n - k 個(gè)元素，逐個(gè)判斷其與堆頂元素的大小蚂四，當(dāng)前元素小時(shí)光戈，取出堆頂，加入當(dāng)前元素(堆調(diào)整)
    • 最終堆中剩余的 k 個(gè)元素就是TopK
  • 方式二：結(jié)果為堆中每次取出的元素
    • 對(duì)于多個(gè)序列的TopK問題遂赠，如本題是有兩個(gè)獨(dú)立的數(shù)組久妆，需要先對(duì)各個(gè)子序列排序
    • 接著同樣在小根堆(升序)中維護(hù)對(duì)應(yīng)序列個(gè)數(shù)個(gè)元素，然后每次取出堆頂元素跷睦，并加入當(dāng)前堆頂元素(最小值)所在序列的下一個(gè)值筷弦，一共進(jìn)行 k 次
    • 取出的元素組成的集合( k 個(gè))就是TopK，這種方式也成為多路歸并抑诸，常見于大文件排序奸笤、海量數(shù)據(jù)排序等場景(面試熱點(diǎn))

• 本題的解題步驟

  • 本題對(duì)應(yīng)第二種方式的情況，但由于本題求解的數(shù)對(duì)哼鬓，所以與普通的解法有一點(diǎn)區(qū)別
  • 由于本題給出的兩個(gè)數(shù)組都是升序數(shù)組监右，可以發(fā)現(xiàn)，數(shù)對(duì)(num1[0], nums2[0])是最小的數(shù)對(duì)异希，且對(duì)于 nums1 中的一個(gè)元素健盒，其與 nums2 中每個(gè)元素組成的數(shù)對(duì)序列也是升序的，反之亦然
  • 因此称簿，當(dāng)求解過程中確定了 (num1[i], nums2[j]) 為一個(gè) TopK后扣癣，下一個(gè)TopK應(yīng)該是從堆中已有元素和 (num1[i+1], nums2[j])、(num1[i], nums2[j+1]) 中產(chǎn)生
  • 首先我們將 k 個(gè)元素放入小根堆中憨降，為了避免后續(xù)查找TopK時(shí)加入元素重復(fù)的問題父虑，初始時(shí)以其中一個(gè)數(shù)組為基礎(chǔ)，加入(0,0), (1,0), ... , (k-1, 0)這些元素授药，當(dāng)取出一個(gè)元素 (i, j) 后士嚎，新加入的元素為(i, j + 1)
  • 取出的元素組成的就是TopK集合

• 題解

  public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
      if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return null;
      List<List<Integer>> smallestPairs = new ArrayList<>();
      int n = nums1.length;
      int m = nums2.length;
      PriorityQueue<int[]> queue = new PriorityQueue<>(k, (a, b) -> (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]]));
      // 1. 維護(hù) K 個(gè)元素到堆中 : (i, 0)
      for (int i = 0; i < Math.min(n, k); i++) {
          queue.add(new int[]{i, 0});
      }
      // 2. 取出堆頂元素并加入新元素
      while (k > 0 && !queue.isEmpty()) {
          int[] pairs = queue.poll();
          List<Integer> list = new ArrayList<>();
          list.add(nums1[pairs[0]]);
          list.add(nums2[pairs[1]]);
          smallestPairs.add(list);
          if(pairs[1] + 1 < m) queue.add(new int[]{pairs[0], pairs[1] + 1});
          k--;
      }
      return smallestPairs;
  }
  

• 復(fù)雜度分析：n 和 m 分別是兩個(gè)數(shù)組的大小，k 是要求的數(shù)對(duì)個(gè)數(shù)

  • 時(shí)間復(fù)雜度：悔叽，初始堆莱衩，堆調(diào)整
  • 空間復(fù)雜度：

3. 方法二：二分 & 滑動(dòng)窗口

• 思路：通過二分確定序列前 k 個(gè)數(shù)對(duì)與后面的分界點(diǎn)的值

  • TopK問題也可以通過二分的思路來解決，因?yàn)閿?shù)對(duì)序列可以等效為類似坐標(biāo)軸的概念娇澎，一定存在一個(gè)分界點(diǎn)笨蚁，將前 k 個(gè)元素與后面的序列分開
  • 數(shù)對(duì)的最小值為，最大值為
  • 可以將最小值最大值作為左右起點(diǎn)，可通過二分查找括细，注意查找的條件不是找到滿足大小關(guān)系的目標(biāo)值伪很，而是找到某個(gè)確保前面有 k 個(gè)，或者算上自身有 k 個(gè)數(shù)對(duì)元素的分界值divideNum
  • 二分法中奋单，計(jì)算小于 mid 值的數(shù)對(duì)元素個(gè)數(shù)可以通過滑動(dòng)窗口的方式锉试，計(jì)算元素個(gè)數(shù)的復(fù)雜度為，整個(gè)二分過程的復(fù)雜度為
  • 找到分界值后辱匿，就可以遍歷兩個(gè)有序數(shù)組键痛，將大小小于分界值的數(shù)對(duì)加入到結(jié)果集中，如果此時(shí)不足 k 個(gè)元素匾七，則考慮將等于分界值的部分?jǐn)?shù)對(duì)加入到結(jié)果集中絮短，因?yàn)橐还惨尤?k 個(gè)數(shù)對(duì)，復(fù)雜度為
  • 注意：本題輸出的順序優(yōu)先輸出小索引的nums1數(shù)組昨忆，所以對(duì)于等于分界值的情況要注意查找的順序

• 題解：直接模擬

  // 方法二：二分 & 滑動(dòng)窗口
  public List<List<Integer>> kSmallestPairs2(int[] nums1, int[] nums2, int k) {
      if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return null;
      List<List<Integer>> smallestPairs = new ArrayList<>();
      int n = nums1.length;
      int m = nums2.length;
  
      // 二分查找第 k 小的數(shù)對(duì)和的大小
      int left = nums1[0] + nums2[0];
      int right = nums1[n - 1] + nums2[m - 1];
      while (left < right) {
          int mid = left + ((right - left) >> 1);
          long count = 0; // mid之前的元素的個(gè)數(shù)
          int start = 0;
          int end = m - 1;
          // 雙指針查找當(dāng)前比 mid 小的元素個(gè)數(shù)丁频，用來確定二分的方向
          while (start < n && end >= 0) {
              if(count >= k) break;
              if (nums1[start] + nums2[end] > mid) {
                  end--;
              } else {
                  count += end + 1;
                  start++;
              }
          }
          // mid前的元素超過k個(gè)，向左二分邑贴，沒超過向右
          if (count < k) {
              left = mid + 1;
          } else {
              right = mid;
          }
      }
  
      // 分界點(diǎn)的值
      int divideNum = left;
      // 找到小于分界點(diǎn)的值的數(shù)對(duì)席里，并添加到TopK中
  
      for (int num1 : nums1) {
          for (int num2 : nums2) {
              if( k > 0 && num1 + num2 < divideNum) {
                  List<Integer> list = new ArrayList<>();
                  list.add(num1);
                  list.add(num2);
                  smallestPairs.add(list);
                  k--;
              }else break;
          }
      }
  
      // 找到等于分界點(diǎn)的值的數(shù)對(duì)
      int index = m - 1;
      for (int i = 0; i < n && k > 0; i++) {
          // 找到第一個(gè)不大于分界點(diǎn)值的數(shù)對(duì)
          while (index >= 0 && nums1[i] + nums2[index] > divideNum) {
              index--;
          }
          for (int j = i; j >= 0; j--) {
              if(k > 0 && nums1[j] + nums2[index] == divideNum) {
                  List<Integer> list = new ArrayList<>();
                  list.add(nums1[j]);
                  list.add(nums2[index]);
                  smallestPairs.add(list);
                  k--;
              }else break;
          }
      }
      return smallestPairs;
  }
  

• 復(fù)雜度分析：n 和 m 分別是兩個(gè)數(shù)組的大小，k 是要求的數(shù)對(duì)個(gè)數(shù)

  • 時(shí)間復(fù)雜度：
  • 空間復(fù)雜度：

最后

如果本文有所幫助的話拢驾，歡迎大家可以給個(gè)三連「點(diǎn)贊」&「收藏」&「關(guān)注」 ~ ~ ~
也希望大家有空的時(shí)候光臨我的其他平臺(tái)奖磁，上面會(huì)更新Java面經(jīng)、八股文繁疤、刷題記錄等等咖为，歡迎大家光臨交流，謝謝稠腊！

• 「個(gè)人博客」
• 「掘金」
• 「LeetCode」