付费阅读下载网站开发,wordpress安装主题之后首页不变,重庆企业seo网络推广外包,高端网站建设公司推荐本文涉及的基础知识点
二分查找算法合集
题目
给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k #xff0c;请你返回第 k #xff08;从 1 开始编号#xff09;小的 nums1[i] * nums2[j] 的乘积#xff0c;其中 0 i nums1.…本文涉及的基础知识点
二分查找算法合集
题目
给你两个 从小到大排好序 且下标从 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 6nums1[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 -16nums1[0] * nums2[0] (-4) * 2 -8nums1[1] * nums2[1] (-2) * 4 -8nums1[1] * nums2[0] (-2) * 2 -4nums1[2] * nums2[0] 0 * 2 0nums1[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 -10nums1[0] * nums2[3] (-2) * 4 -8nums1[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 是两个数组的最大值。
分情况讨论
结果数组一数组二负数负数正数负数正数负数00任意数0非00正数正数正数正数负数负数
第一层二分
寻找一个符合如下条件的llMul 乘积小于等于llMul的组合数量大于等于k。 左开右闭空间。
负数的问题
如果乘积为负数第k小则绝对值第k大。我们可以负数全部转成绝对值然后倒序这样可以保证升序。m个数第k大从1开始就是m-k1小。
变量解释
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( vectorint nums1, vectorint 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( vectorint nums1, vectorint 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 全部小于等于llMulright--;}llCnt (right1);}return llCnt;}优化三
0不必单独考虑。0符合负数的规则绝对值越大乘积越小。0也符合正数的规则觉得值越大乘积越大。
class Solution {
public:long long kthSmallestProduct(vectorint nums1, vectorint nums2, long long k) {auto it1 std::lower_bound(nums1.begin(), nums1.end(), 0);auto it2 std::lower_bound(nums2.begin(), nums2.end(), 0);vectorint v12(it1, nums1.end());vectorint v22(it2, nums2.end());vectorint v11 CopyAndMul(vectorint(nums1.begin(), it1));vectorint v21 CopyAndMul(vectorint(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( vectorint nums11, vectorint nums12, vectorint nums21, vectorint 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( vectorint nums1, vectorint 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 全部小于等于llMulright--;}llCnt (right1);}return llCnt;}vectorint CopyAndMul(const vectorint nums){vectorint 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_iMoreEqualNum0; };
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 C17 或者 操作系统win10 开发环境
VS2022 C17
