一道综合题

$有两个数组长度为n的数组a和b,现在从a中任选一个数,b中任选一个数,两数相乘,求第k小的数$

例: $a=[1, 2, 3], b = [2, 3, 4]$

第二小的为$3$

• 当a, b值域为$[0, 10^4]$时,$n = 100$时

• 当a, b值域为$[0, 10^4]$时, $n = 5000$时

• 当a, b值域为$[-10^8, 10^8]$时, $n = 10^5$时

• 当$n = 2 *10^6$时

• 对于第一种解法,n和值域都很小,显然可以使用暴力做:

  public long func(int[] nums1, int[] nums2, int k) {
         return Arrays.stream(nums1)
                 .flatMap(a -> Arrays.stream(nums2).map(b -> a * b))
                 .sorted().boxed().toList().get(k - 1);
     }

• 对于第二种情况而言,如果还采用第一种解法,先暴力匹配枚举,然后排序找到第k小,时间复杂度为$n^2 + log n$,数量级已经超过$10^7$,不是一种很好的做法,如果我们能把时间复杂度控制在$nlogn$就很棒了。事实上我们可以采用多路归并算法,省去$n^2$的匹配,时间复杂度为$klogn$(可以根据k的大小判断小根堆还是大根堆),但下面代码这种做法有一个前提条件必须值域为非负数,因为如果存在负数的话,按照从小到大的排序,但两个负数乘积却为正数,我们无法按照正常多路归并的算法执行，虽然对于这种情况也有处理方式，但太麻烦了。

  public long func(int[] nums1, int[] nums2, long k) {
      Arrays.sort(nums1);
      Arrays.sort(nums2);
      PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparing(e -> (nums1[e[0]] * nums2[e[1]])));
      int n = nums1.length;
      for (int i = 0; i < n; i++) {
          heap.add(new int[] {0, i});
      }
      int ans = 0;
      for (int i = 0; i < k; i++) {
          var poll = heap.poll();
          int x = poll[0], y = poll[1];
          ans = nums1[x] * nums2[y];
          if (x + 1 < n) heap.add(new int[] {x + 1, y});
      }
      return ans;
  }

• 然而对于第三种情况而言数组的长度达到了$10^5$,且值域达到$[-10^8, 10^8]$,显然上面两种做法是不可取的(通常而言当计算出时间复杂度为$10^8$以上的时候,基本就不是正解)，我们需要换一种方式，对于前两种解法我们都是考虑数组长度和k的关系,当这种思路已经无法再继续优化的时候,我们可以尝试换种思路,对于这道题而言,我们就剩没考虑值域了,事实上我们可以从值域出发,直接算出第k个值为多少,当然,一个一个枚举的做法显然也是行不通的,仔细研究题目我们就会发现可以通过二分查找(必须掌握)找到第k个值,那么该怎样check呢?显然check的时间复杂度不能为$n^2$,我们再仔细研究题目,因为check的时候是要判断有多少个数大于或小于二分所枚举的x,因此我们还可以使用二分,枚举第一个数组的数,二分查找查找第二个数组有多少个符合的数，因为存在负数,这里的二分要分不同情况。时间复杂度$nlog n logU$

  class Solution {
  
      int[] nums1, nums2;
  
      long k;
      public long fun(int[] nums1, int[] nums2, long k) {
          long l = (long) -1e18, r = (long) 1e18;
          this.nums1 = nums1;
          this.nums2 = nums2;
          this.k = k;
          Arrays.sort(nums1);
          Arrays.sort(nums2);
          while (l < r) {
              long mid = l + r >> 1;
              if (check(mid)) {
                  r = mid;
              } else l = mid + 1;
          }
          return l;
      }
  
      boolean check(long x) {
          long cnt = 0;
          for (int i = 0; i < nums1.length; i++) {
              if (nums1[i] < 0) {
                  if ((long) nums1[i] * nums2[0] <= x) {
                      cnt += nums2.length;
                      continue;
                  } else {
                      cnt += check1(nums1[i], x);
                  }
              } else if (nums1[i] > 0) {
                  if ((long) nums1[i] * nums2[nums2.length - 1] <= x) {
                      cnt += nums2.length;
                      continue;
                  } else {
                      cnt += check2(nums1[i], x);
                  }
              } else {
                  if (x >= 0) cnt += nums2.length;
              }
          }
          return cnt >= k;
      }
  
  
      int check1(int v, long x) {
          int l = 0, r = nums2.length - 1;
          while (l < r) {
              int mid = l + r >> 1;
              if ((long) nums2[mid] * v <= x) r = mid;
              else l = mid + 1;
          }
          if ((long) nums2[l] * v <= x) {
              return nums2.length - l;
          }
          return 0;
      }
  
  
      int check2(int v, long x) {
          int l = 0, r = nums2.length - 1;
          while (l < r) {
              int mid = l + r + 1 >> 1;
              if ((long) nums2[mid] * v <= x) l = mid;
              else r = mid - 1;
          }
          if ((long) nums2[l] * v <= x) {
              return l + 1;
          }
          return 0;
      }
  }

• 最后一种需要用一种非常难的算法,不做解释,希望掌握前三种情况的解法,对于不同的范围,我们需要深刻理解题目本质，掌握基础算法，合理分析复杂度，写出一个完美的代码.