文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你兩個 從小到大排好序 且下標從 0 開始的整數數組 nums1 和 nums2 以及一個整數 k ，請你返回第 k （從 1 開始編號）小的 nums1[i] * nums2[j] 的乘積，其中 0 <= i < nums1.length 且 0 <= j < nums2.length 。

示例 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 都是從小到大排好序的。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/kth-smallest-product-of-two-sorted-arrays
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 二分查找答案 ans，檢查兩個數組組成的乘積 <= ans 的個數 ct 是否滿足 k 個，具有單調性

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]);elsezero.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;}elsel = 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;} };

1788 ms 91.9 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 2040. 两个有序数组的第 K 小乘积（嵌套二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。