1. Toy模板网首页
  2. > Toy博客

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积

8月前 作者：闻缺陷则喜何志丹 分类：Toy博客 阅读(30) 违法举报

这篇具有很好参考价值的文章主要介绍了[二分查找]LeetCode2040:两个有序数组的第 K 小乘积。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本文涉及的基础知识点

二分查找算法合集

题目

给你两个 从小到大排好序 且下标从 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 * 104
    -105 <= nums1[i], nums2[j] <= 105
    1 <= k <= nums1.length * nums2.length
    nums1 和 nums2 都是从小到大排好序的。

两层二分查找

时间复杂度

O(log(max2)nlogn),n是两个数组长度的较大者，max 是两个数组的最大值。

分情况讨论

结果 数组一 数组二
负数 负数 正数
负数 正数 负数
0 0 任意数
0 非0 0
正数 正数 正数
正数 负数 负数

第一层二分

寻找一个符合如下条件的llMul：
乘积小于等于llMul的组合数量大于等于k。
左开右闭空间。

负数的问题

如果乘积为负数，第k小则绝对值第k大。我们可以负数全部转成绝对值，然后倒序，这样可以保证升序。m个数，第k大（从1开始），就是m-k+1小。

变量解释
v11 数组一中的负数的绝对值，升序
v12 数组一中的正数，升序
v21 数组二中的负数的绝对值，升序
v22 数组二中的正数，升序

代码

核心代码

class Solution {
public:
long long kthSmallestProduct(vector& nums1, vector& nums2, long long k) {
auto it1 = std::equal_range(nums1.begin(), nums1.end(), 0);
auto it2 = std::equal_range(nums2.begin(), nums2.end(), 0);
const long long less0Count1 = it1.first - nums1.begin();
const long long i0Count1 = it1.second - it1.first;
const long long great0Count1 = nums1.end() - it1.second;
const long long less0Count2 = it2.first - nums2.begin();
const long long i0Count2 = it2.second - it2.first;
const long long great0Count2 = nums2.end() - it2.second;
const long long llZeroCount = i0Count1 * nums2.size() + i0Count2 * nums1.size() - i0Count1 * i0Count2;
const long long llLess0Cout = less0Count1 * great0Count2 + less0Count2 * great0Count1;
vector v12(it1.second, nums1.end());
vector v22(it2.second, nums2.end());
vector v11 = CopyAndMul(vector(nums1.begin(), it1.first));
vector v21 = CopyAndMul(vector(nums2.begin(), it2.first));
if (k <= llLess0Cout)
{//在负数中找
k = llLess0Cout + 1 - k;
return -DoGreate0(v11, v22, v21, v12, k);
}
k -= llLess0Cout;
if (k <= llZeroCount)
{
return 0;
}
k -= llZeroCount;
return DoGreate0(v11, v21,v12, v22,k);
}
//从升序正数数组中寻找第k小的积： 第一个积小于等于llMul 的数量大于等于k 左开右闭
long long DoGreate0(const vector& nums11,const vector& nums12, const vector& nums21, const vector& nums22, long long k)
{
long long left = 0, right = (long long) 1e10;
while (right - left > 1)
{
const auto mid = left + (right - left) / 2;
int iCnt = 0;
const long long llHas = LessEqual(nums11, nums12, mid) + LessEqual(nums21, nums22, mid);
if (llHas >= k)
{
right = mid;
}
else
{
left = mid;
}
}
return right;
}
long long LessEqual(const vector& nums1, const vector& nums2, long long llMul)
{
long long llCnt = 0;
for (const auto& n : nums2)
{
llCnt += std::upper_bound(nums1.begin(), nums1.end(), llMul / n) - nums1.begin();
}
return llCnt;
}
vector CopyAndMul(const vector& nums)
{
vector vRet(nums.size());
for (int i = 0; i < nums.size(); i++)
{
vRet[i] = -nums[nums.size() - 1 - i];
}
return vRet;
}
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
vector nums1, nums2;
long long k, res;
{
nums1 = { -2,-1 }, nums2 = { -2,-1 }, k = 4;
Solution slu;
auto res = slu.kthSmallestProduct(nums1, nums2, k);
Assert(4LL, res);
}
{
nums1 = { 2, 5 }, nums2 = { 3, 4 }, k = 2;
Solution slu;
auto res = slu.kthSmallestProduct(nums1, nums2, k);
Assert(8LL, res);
}
{
nums1 = { -4,-2,0,3 }, nums2 = { 2,4 }, k = 6;
Solution slu;
auto res = slu.kthSmallestProduct(nums1, nums2, k);
Assert(0LL, res);
}
{
nums1 = { -2,-1,0,1,2 }, nums2 = { -3,-1,2,4,5 }, k = 3;
Solution slu;
auto res = slu.kthSmallestProduct(nums1, nums2, k);
Assert(-6LL, res);
}
{
nums1 = { 0 }, nums2 = { 0,0,0}, k = 3;
Solution slu;
auto res = slu.kthSmallestProduct(nums1, nums2, k);
Assert(0LL, res);
}
{
nums1 = { 1,2 }, nums2 = { 1,2}, k = 3;
Solution slu;
auto res = slu.kthSmallestProduct(nums1, nums2, k);
Assert(2LL, res);
}
{
nums1 = { 1,10000 };
nums2 = { 1,10000 };
k = 4;
Solution slu;
auto res = slu.kthSmallestProduct(nums1, nums2, k);
Assert(10000* 10000LL, res);
}

//CConsole::Out(res);

}

优化一

确保数组二的长度比数组一短

if (nums1.size() < nums2.size())
		{
			swap(nums1, nums2);
		}

完整函数：

	long long LessEqual( vector<int>& nums1,  vector<int>& nums2, long long llMul)
	{
		if (nums1.size() < nums2.size())
		{
			swap(nums1, nums2);
		}
		long long llCnt = 0;
		for (const auto& n : nums2)
		{
			llCnt += std::upper_bound(nums1.begin(), nums1.end(), llMul / n) - nums1.begin();
		}
		return llCnt;
	}

优化二

第二层二分查找可以优化成双指针。这样也不用思考取整之类，容易理解。

	long long LessEqual( vector<int>& nums1,  vector<int>& nums2, long long llMul)
	{
		long long llCnt = 0;
		int right = nums1.size()-1;
		for (const auto& n : nums2)
		{
			while ((right >=0 ) && (nums1[right] * (long long)n > llMul))
			{//nums1[0,right]*n 全部小于等于llMul
				right--;
			}
			llCnt += (right+1);
		}
		return llCnt;
	}

优化三

0不必单独考虑。0符合负数的规则：绝对值越大，乘积越小。0也符合正数的规则，觉得值越大，乘积越大。

class Solution {
public:
	long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
		auto it1 = std::lower_bound(nums1.begin(), nums1.end(), 0);
		auto it2 = std::lower_bound(nums2.begin(), nums2.end(), 0);
		vector<int> v12(it1, nums1.end());
		vector<int> v22(it2, nums2.end());
		vector<int> v11 = CopyAndMul(vector<int>(nums1.begin(), it1));
		vector<int> v21 = CopyAndMul(vector<int>(nums2.begin(), it2));
		const long long ll24Count = v11.size() * (long long)v22.size() + (long long)v12.size() * v21.size();
		if (k <= ll24Count)
		{//在负数中找
			k = ll24Count + 1 - k;
			return -DoGreate0(v11, v22, v21, v12, k);
		}
		k -= ll24Count;	
		return DoGreate0(v11, v21,v12, v22,k);
	}
	//从升序正数数组中寻找第k小的积： 第一个积小于等于llMul 的数量大于等于k 左开右闭
	long long DoGreate0( vector<int>& nums11, vector<int>& nums12,  vector<int>& nums21,  vector<int>& nums22, long long k)
	{
		long long left = -1, right = (long long) 1e10;
		while (right - left > 1)
		{
			const auto mid = left + (right - left) / 2;
			const long long llHas = LessEqual(nums11, nums12, mid) + LessEqual(nums21, nums22, mid);
			if (llHas >= k)
			{
				right = mid;
			}
			else
			{
				left = mid;
			}
		}
		return right;
	}
	long long LessEqual( vector<int>& nums1,  vector<int>& nums2, long long llMul)
	{
		long long llCnt = 0;
		int right = nums1.size()-1;
		for (const auto& n : nums2)
		{
			while ((right >=0 ) && (nums1[right] * (long long)n > llMul))
			{//nums1[0,right]*n 全部小于等于llMul
				right--;
			}
			llCnt += (right+1);
		}
		return llCnt;
	}
	vector<int> CopyAndMul(const vector<int>& nums)
	{
		vector<int> vRet(nums.size());
		for (int i = 0; i < nums.size(); i++)
		{
			vRet[i] = -nums[nums.size() - 1 - i];
		}
		return vRet;
	}
};

2023年3月版

class CNumHelp
{
public:
CNumHelp(vector& nums) :m_nums(nums)
{
auto it1 = std::equal_range(m_nums.begin(), m_nums.end(), 0);
m_iLess0Num = it1.first - m_nums.begin();
m_i0Num = it1.second - it1.first;
m_iMore0Num = m_nums.end() - it1.second;
m_iLessEqual0Num = m_iLess0Num + m_i0Num;
m_iMoreEqualNum = m_iMore0Num + m_i0Num;
}
vector m_nums;
int m_iLess0Num = 0, m_i0Num = 0, m_iMore0Num = 0;
int m_iLessEqual0Num = 0,m_iMoreEqualNum=0;
};

class ICal
{
public:
virtual long long Cal(long long llMid)const = 0;
};
class CCalMore0 : public ICal
{
public:
CCalMore0(const CNumHelp& help1, const CNumHelp& help2) :m_help1(help1), m_help2(help2)
{

 }
 virtual long long Cal(long long llMid)const
 {
	 long long llNum = 0;
	 for (int i = m_help1.m_iLessEqual0Num; i < m_help1.m_nums.size(); i++)
	 {
		 int iCurNum = std::upper_bound(m_help2.m_nums.begin(), m_help2.m_nums.end(), llMid / m_help1.m_nums[i]) - m_help2.m_nums.begin() - m_help2.m_iLessEqual0Num;
		 llNum += iCurNum;
	 }

	 for (int i = 0; i < m_help1.m_iLess0Num; i++)
	 {
		 auto it = std::equal_range(m_help2.m_nums.begin(), m_help2.m_nums.end(), llMid / m_help1.m_nums[i]);
		 //auto it2 = (0 == llMid % m_help1.m_nums[i]) ? it.first : it.second;
		 auto it2 = it.first;
		 llNum += m_help2.m_nums.end() - it2 - m_help2.m_iMoreEqualNum;
	 }
	 return llNum;
 }

private:

 const CNumHelp m_help1;
 const CNumHelp m_help2;

};

class CCalLess0 : public ICal
{
public:
CCalLess0(const CNumHelp& help1, const CNumHelp& help2) :m_help1(help1), m_help2(help2)
{
}
virtual long long Cal(long long llMid)const
{
return Cal(llMid, m_help1, m_help2) + Cal(llMid, m_help2, m_help1);
}
static long long Cal(long long llMid, const CNumHelp& help1, const CNumHelp& help2)
{
long long llNum = 0;
for (int i = help1.m_iLessEqual0Num; i < help1.m_nums.size(); i++)
{
auto it = std::equal_range(help2.m_nums.begin(), help2.m_nums.end(), llMid / help1.m_nums[i]);
auto it2 = (0 == llMid% help1.m_nums[i]) ? it.second : it.first;
int iCurNum = it2 -help2.m_nums.begin();
llNum += iCurNum;
}
return llNum;
}
private:
const CNumHelp m_help1;
const CNumHelp m_help2;
};
class Solution {
public:
long long kthSmallestProduct(vector& nums1, vector& nums2, long long k) {
CNumHelp help1(nums1), help2(nums2);
//const long long llTotal = (long long)nums1.size()nums2.size();
const long long ll0Num = (long long)help1.m_i0Num * nums2.size() + (long long)help2.m_i0Num * nums1.size() - (long long)help1.m_i0Numhelp2.m_i0Num;
const long long llLess0Num = (long long)help1.m_iMore0Num * help2.m_iLess0Num + (long long)help1.m_iLess0Num * help2.m_iMore0Num;
if (k <= llLess0Num)
{
CCalLess0 cal(help1, help2);
return Do(cal, k, (long long)100000 * -100000 - 1,-1);
}
k -= llLess0Num;
if (k <= ll0Num)
{
return 0;
}
k -= ll0Num;
CCalMore0 cal(help1, help2);
return Do(cal, k, 0, (long long)100000 * 100000);
}
long long Do(const ICal& cal, long long k, long long left, long right)
{
while (right > left + 1)
{
const auto llMid = left + (right - left) / 2;
const long long llNum = cal.Cal(llMid);
if (llNum >= k)
{
right = llMid;
}
else
{
left = llMid;
}
}
return right;
}

};

2023年9月

class Solution {
public:
long long kthSmallestProduct(const vector& nums1, const vector& nums2, long long k) {
CalRange(nums1, m_v11, m_v12);
CalRange(nums2, m_v21, m_v22);
const int iZero1Num = nums1.size() - m_v11.size() - m_v12.size();
const int iZero2Num = nums2.size() - m_v21.size() - m_v22.size();
long long llLess0 = (long long)m_v11.size() * m_v22.size() + (long long)m_v21.size() * m_v12.size();
long long ll0 = (long long)nums2.size() * iZero1Num + (long long)nums1.size() * iZero2Num - (long long)iZero1Num * iZero2Num;
if (k <= llLess0)
{//结果是负数
m_v21.swap(m_v22);
return -Do(llLess0 - k + 1);
}
k -= llLess0;
if (k <= ll0)
{
return 0;
}
k -= ll0;
return Do(k);
}
long long Do(long long k)
{
long long left =-(1e10 + 0.5)-1, r = 1e10 + 0.5;
while (r - left > 1)
{
const auto mid = left + (r - left) / 2;
long long llNum = CountEqualLess(m_v11, m_v21,mid) + CountEqualLess(m_v12, m_v22,mid);
if (llNum >= k)
{
r = mid;
}
else
{
left = mid;
}
}
return r;
}
long long CountEqualLess(const vector& nums1, const vector& nums2, long long llMul)
{
long long llCnt = 0;
int r = 0 ;//[0,r)和num2[i]的乘积 < llMul
for (int i =nums2.size()-1; i >= 0 ;i-- )
{
for (; (r < nums1.size() ) && ((long long)nums1[r] * nums2[i] <= llMul); r++);
llCnt += r;
}
return llCnt;
}
static void CalRange(const vector& nums, vector& v1, vector& v2)
{
int i = 0;
for (i = 0; (i < nums.size()) && (nums[i] < 0); i++)
{
v1.emplace_back(-nums[i]);
}
std::reverse(v1.begin(), v1.end());
for (; (i < nums.size()) && (nums[i] == 0); i++);
for (; i < nums.size(); i++)
{
v2.emplace_back(nums[i]);
}
}
vector m_v11, m_v12, m_v21, m_v22;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：

VS2022 C++17

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积,# 算法题,数据结构与算法,算法,c++,LeetCode,二分查找,乘积,第k小,有序数组文章来源地址https://www.toymoban.com/news/detail-758949.html

到了这里，关于[二分查找]LeetCode2040:两个有序数组的第 K 小乘积的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 二分查找实例1（在排序数组中查找元素的第一个和最后一个位置）

    二分查找实例1（在排序数组中查找元素的第一个和最后一个位置）

    给你一个按照非递减顺序排列的整数数组  nums ，和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ，返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1： 示例 2： 示例 3： 提示

    2024年02月09日
    浏览(32)

  • 二分查找两个模板，leetcode35.搜索插入位置

    在有序数列中，查找某个元素是否存在 扩展一下： 在有序数列中(通常是非递减，可以有重复元素)，查找第一个满足xx条件的元素 每次搜索区间减半，时间复杂度 O ( l o g n ) O(logn) O ( l o g n ) 1.初始边界为0和n-1，如果你的下标从1开始，那就是1和n，效果一样， 只需要确保初始

    2024年02月20日
    浏览(32)
  • Leetcode. 88合并两个有序数组

    Leetcode. 88合并两个有序数组

    合并两个有序数组 核心思路： 依次比较，取较小值放入新数组中 i 遍历nums1 ， j 遍历nums2 ，取较小值放入nums3中 那如果nums[i] 和nums[j]中相等，随便放一个到nums3 那如果nums[i] 和nums[j]中相等，随便放一个到nums3 此时 nums1 中的元素已经走完了，那么直接把 nums2 中剩下的元素拿到

    2023年04月08日
    浏览(90)

  • 【Leetcode】88.合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2 ，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意 ：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况

    2024年02月12日
    浏览(33)

  • leetcode 88 合并两个有序数组

    题目描述： 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应

    2024年02月03日
    浏览(36)
  • LeetCode88——合并两个有序数组

    LeetCode88——合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。 为了应对这种情况

    2024年02月08日
    浏览(28)

  • LeetCode 0088. 合并两个有序数组

    力扣题目链接：https://leetcode.cn/problems/merge-sorted-array/ 给你两个按 非递减顺序 排列的整数数组  nums1 和 nums2 ，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意： 最终，合并后数组不应由

    2024年02月13日
    浏览(42)

  • LeetCode_88. 合并两个有序数组

    目录 题目描述 思路分析 我的题解 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意：最终，合并后数组不应由函数返回，而是存储

    2023年04月15日
    浏览(34)
  • 【LeetCode】移除元素、删除有序数组中的重复项、合并两个有序数组

    【LeetCode】移除元素、删除有序数组中的重复项、合并两个有序数组

    🧑‍💻作者： @情话0.0 📝专栏：《LeetCode》 🔖题目链接：移除元素、删除有序数组中的重复项、合并两个有序数组 给你一个数组 nums 和一个值 val，你需要 原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空

    2023年04月09日
    浏览(39)
  • Leetcode每日一题——“合并两个有序数组”

    Leetcode每日一题——“合并两个有序数组”

    各位CSDN的uu们你们好呀，又到小雅兰的愉快题解时候啦，今天，我们的题目内容是合并两个有序数组，下面，让我们进入合并两个有序数组的世界吧 示例 1： 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [ 1,2

    2023年04月24日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包