LeetCode 2040. 两个有序数组的第 K 小乘积（嵌套二分查找）

示例 1：
输入：nums1 = [2,5], nums2 = [3,4], k = 2
输出：8
解释：第 2 小的乘积计算如下：
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
第 2 小的乘积为 8 。
示例 2：
输入：nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
输出：0
解释：第 6 小的乘积计算如下：
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
第 6 小的乘积为 0 。
示例 3：
输入：nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
输出：-6
解释：第 3 小的乘积计算如下：
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
第 3 小的乘积为 -6 。
提示：
1 <= nums1.length, nums2.length <= 5 * 10^4
-10^5 <= nums1[i], nums2[j] <= 10^5
1 <= k <= nums1.length * nums2.length
nums1 和 nums2 都是从小到大排好序的。

class Solution {
    vector<int> neg, zero, pos; // 数组2拆分为三部分 - 0 +
public:
    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        long long l = -1e10, r = 1e10, mid, ans;
        for(int i = 0; i < nums2.size(); ++i)
        {
            if(nums2[i] < 0)
                neg.push_back(nums2[i]);
            else if(nums2[i] > 0)
                pos.push_back(nums2[i]);
            else
                zero.push_back(nums2[i]);
        }
        while(l <= r) // 二分查找答案
        {
            mid = l+((r-l)>>1);
            long long ct = check(nums1, nums2, mid);
            if(ct >= k)
            {
                ans = mid;
                r = mid-1;
            }
            else
                l = mid+1;
        }
        return ans;
    }
    long long check(vector<int>& nums1, vector<int>& nums2, long long num)
    {
        long long ct = 0; // 计算有多少数是小于等于 num 的
        for(auto a : nums1)
        {
            if(a == 0)
            {
                if(num >= 0)
                    ct += nums2.size();
            }
            else if(a > 0)
            {
                if(num == 0)
                    ct += neg.size()+zero.size();
                else if(num > 0)
                {
                    auto x = upper_bound(pos.begin(), pos.end(), num/a);
                    ct += x-pos.begin()+neg.size()+zero.size();
                }
                else
                {
                    long long t = num%a ? num/a-1 : num/a;
                    auto x = upper_bound(neg.begin(), neg.end(), t);
                    ct += x-neg.begin();
                }
            }
            else // a < 0
            {
                if(num == 0)
                    ct += pos.size()+zero.size();
                else if(num > 0)
                {
                    auto x = lower_bound(neg.begin(), neg.end(), num/a);
                    ct += neg.end()-x+pos.size()+zero.size();
                }
                else
                {
                    long long t = num%a ? num/a+1 : num/a;
                    auto x = lower_bound(pos.begin(), pos.end(), t);
                    ct += pos.end()-x;
                }
            }
        }
        return ct;
    }
};