2040. Kth Smallest Product of Two Sorted Arrays
思路 :
这题就对答案进行binary search
假设nums1有n个元素、nums2有m个元素
找出第k小的乘积
也就是会有 n*m - k个乘积比他大
问题变成在binary search中要如何快速找到比mid大的数有几个
不可能每次都去把所有乘积算一次
先把nums1、nums2分成全部为正数/负数的 pos1、nag1、pos2、nag2
以pos1、pos2举例
pos1 = [1,2,3,4,5]、pos2=[1,2,3,4,5]
如果要找比4大的乘积有几个
pos1[0] * pos2[4] = 5 > 4
而pos1[1] > pos1[0] 所以 pos1[1] * pos2[4] 一定大于 4
这样就不用算 pos[1] * pos2[4]的乘积，直接从pos[1] * pos2[3]继续算下去就好
基本上剩下的组合 (pos1,nag2)、(nag1,pos2)、(nag1,nag2)都有类似的关系
知道后就是简单的bunary search了
c++ code :
long long PosIdx1, PosIdx2;
class Solution {
public:
long long GreaterThanM(vector<int> nums1, vector<int> nums2, long long mid
)
{
long long res = 0;
long long n = nums1.size(), m = nums2.size();
// POSITIVE POSITIVE
int j = m - 1;
for (int i = PosIdx1; i < n; i++) {
while (j >= PosIdx2 && 1LL * nums1[i] * nums2[j] > mid) {
j