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--; } res += m - 1 - j; } // NEGATIVE NEGATIVE j = 0; for (int i = PosIdx1 - 1; i > -1; i--) { while (j < PosIdx2 && 1LL * nums1[i] * nums2[j] > mid) { j++; } res += j; } // NEGATIVE POSITIVE j = PosIdx1 - 1; for (int i = m - 1; i >= PosIdx2; i--) { while (j > -1 && 1LL * nums1[j] * nums2[i] > mid) { j--; } res += PosIdx1 - 1 - j; } // POSITIVE NEGATIVE j = PosIdx2 - 1; for (int i = n - 1; i >= PosIdx1; i--) { while (j > -1 && 1LL * nums1[i] * nums2[j] > mid) { j--; } res += PosIdx2 - 1 - j; } return res; } long long kthSmallestProduct(vector<int> &nums1, vector<int> &nums2, long long k) { PosIdx1 = (long long)(upper_bound(nums1.begin(), nums1.end(), 0) - nums1.begin()); PosIdx2 = (long long)(upper_bound(nums2.begin(), nums2.end(), 0) - nums2.begin()); long long n = nums1.size(), m = nums2.size(); long long target = n * m - k; auto getProd = [&](int i, int j) -> long long { return 1LL * nums1[i] * nums2[j]; }; long long r = max({getProd(n - 1, m - 1), getProd(n - 1, 0), getProd(0 , m - 1), getProd(0, 0)}); long long l = min({getProd(n - 1, m - 1), getProd(n - 1, 0), getProd(0 , m - 1), getProd(0, 0)}); while (r > l) { long long mid = l + (r - l) / 2; long long numGthanM = GreaterThanM(nums1, nums2, mid); if (numGthanM > target) { l = mid + 1; } else { r = mid; } } return l; } }; -- ※ 發信站: 批踢踢實業坊(pttsite.org.tw), 來自: 203.121.235.241 (臺灣) ※ 文章網址: https://pttsite.org.tw/Marginalman/M.1750858772.A.A03