在godaddy做网站贵吗,网络整合营销,网络企业网站建设方案,wordpress 优化变快作者推荐
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
本文涉及的基础知识点
二分查找算法合集 分组 动态规划
题目
给你一个下标从 0 开始包含 n 个正整数的数组 arr #xff0c;和一个正整数 k 。 如果对于每个满足 k i n-1 的下标 i #xff0c;都有…作者推荐
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
本文涉及的基础知识点
二分查找算法合集 分组 动态规划
题目
给你一个下标从 0 开始包含 n 个正整数的数组 arr 和一个正整数 k 。 如果对于每个满足 k i n-1 的下标 i 都有 arr[i-k] arr[i] 那么我们称 arr 是 K 递增 的。 比方说arr [4, 1, 5, 2, 6, 2] 对于 k 2 是 K 递增的因为 arr[0] arr[2] (4 5) arr[1] arr[3] (1 2) arr[2] arr[4] (5 6) arr[3] arr[5] (2 2) 但是相同的数组 arr 对于 k 1 不是 K 递增的因为 arr[0] arr[1]对于 k 3 也不是 K 递增的因为 arr[0] arr[3] 。 每一次 操作 中你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。 请你返回对于给定的 k 使数组变成 K 递增的 最少操作次数 。 示例 1 输入arr [5,4,3,2,1], k 1 输出4 解释 对于 k 1 数组最终必须变成非递减的。 可行的 K 递增结果数组为 [5,6,7,8,9][1,1,1,1,1][2,2,3,4,4] 。它们都需要 4 次操作。 次优解是将数组变成比方说 [6,7,8,9,10] 因为需要 5 次操作。 显然我们无法使用少于 4 次操作将数组变成 K 递增的。 示例 2 输入arr [4,1,5,2,6,2], k 2 输出0 解释 这是题目描述中的例子。 对于每个满足 2 i 5 的下标 i 有 arr[i-2] arr[i] 。 由于给定数组已经是 K 递增的我们不需要进行任何操作。 示例 3 输入arr [4,1,5,2,6,2], k 3 输出2 解释 下标 3 和 5 是仅有的 3 i 5 且不满足 arr[i-3] arr[i] 的下标。 将数组变成 K 递增的方法之一是将 arr[3] 变为 4 且将 arr[5] 变成 5 。 数组变为 [4,1,5,4,6,5] 。 可能有其他方法将数组变为 K 递增的但没有任何一种方法需要的操作次数小于 2 次。 提示 1 arr.length 105 1 arr[i], k arr.length
分析
时间复杂度
O(nlogn)枚举每个元素时间复杂度O(n)每个元素二分查找O(logn)。
代码
原理
一有多少对不符合递增则至少需要多少次操作。arr[i]和arr[i1]不符合需要修改arr[i]或arr[i1]。能否一次修改同时解决两个数对假定arr[i-1] arr[i] arr[i1]由于arr[i-1]arr[i1]所以arr[i]无论如何都不可能大于等于arr[i-1]同时小于等于arr[i1]。 二需要的操作数可能大于非递增的对数。比如4 1 3 4 1非递增1 3递增。 三操作次数等于总元素数-最长递增序列的长度。假定最长子系列为newNew[0]…newNew[n]。 四第三只能说明是一个解现在来证明是最优解 假定arr2最优解删掉修改过的元素那么它一定是arr的子序列且是递增的。此子系列越长删除操作的元素越少。
newNew[0]之前的元素全部改成newNew[0]newNew[n]之后的元素全部改成newNew[n]newNew[i]和newNew[i1]的元素全改成newNew[i]
变量解释
vLenMinEndvLenMinEnd[i]x在长度为i的子序列中结尾的最小值为x
核心代码
class Solution {
public:int kIncreasing(vectorint arr, int k) {int iMaxLen 0;for (int i 0; i k; i){vectorint vLenMinEnd { 0,arr[i] };for (int j i k; j arr.size(); j k){auto index std::upper_bound(vLenMinEnd.begin(), vLenMinEnd.end(), arr[j])- vLenMinEnd.begin();if (index vLenMinEnd.size()){vLenMinEnd.emplace_back(arr[j]);continue;}vLenMinEnd[index] min(vLenMinEnd[index], arr[j]); }iMaxLen vLenMinEnd.size() - 1;}return arr.size()-iMaxLen;}
};测试用例
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 arr; int k, res; { Solution slu; arr { 12, 6, 12, 6, 14, 2, 13, 17, 3, 8, 11, 7, 4, 11, 18, 8, 8, 3 }, k 1; auto res slu.kIncreasing(arr, k); Assert(12, res); } { Solution slu; arr { 5, 4, 3, 2, 1 }, k 1; auto res slu.kIncreasing(arr,k); Assert(4, res); } { Solution slu; arr { 4,1,5,2,6,2 }, k 2; auto res slu.kIncreasing(arr, k); Assert(0, res); } { Solution slu; arr { 4,1,5,2,6,2 }, k 3; auto res slu.kIncreasing(arr, k); Assert(2, res); }
//CConsole::Out(res);}
2023年9月旧代码
class Solution { public: int kIncreasing(vector arr, int k) { vectorvector vSubArr(k); for (int i 0; i arr.size(); i) { vSubArr[i%k].push_back(arr[i]); } int iRet 0; for ( auto v : vSubArr) { iRet NeedChange(v, 0, v.size() ); } return iRet; } int NeedChange(vector arr,int iLeft,int iRight) { std::mapint, int mValueNums; for (const auto a : arr) { auto it mValueNums.upper_bound(a); auto itTmp it; const int iValue ((mValueNums.begin() it) ? 0 : (–itTmp)-second) 1; if ((mValueNums.end() ! it) (it-second iValue)) { mValueNums.erase(it); } mValueNums[a] iValue; } return arr.size() - mValueNums.rbegin()-second; } int m_iK; };
2023年9月第一版
class Solution { public: int kIncreasing(vector arr, int k) { int iRet 0; for (int turn 0; turn k; turn) { std::mapint, int mEndLen; mEndLen[0] 0; int iMaxLen 0; for (int index turn; index arr.size(); index k) { auto it mEndLen.upper_bound(arr[index]); const int iLen std::prev(it)-second1; it mEndLen.lower_bound(arr[index]); auto ij it; for (; (ij ! mEndLen.end()) (ij-second iLen); ij); mEndLen.erase(it, ij); mEndLen[arr[index]] iLen; iMaxLen max(iMaxLen, iLen); } iRet iMaxLen; } return arr.size()- iRet; } };
2023年9月第二版
class Solution { public: int kIncreasing(vector arr, int k) { int iRet 0; for (int turn 0; turn k; turn) { vector vValue; for (int index turn; index arr.size(); index k) { auto it std::upper_bound(vValue.begin(), vValue.end(),arr[index]); if (vValue.end() it) { vValue.emplace_back(arr[index]); } else { *it arr[index]; } } iRet vValue.size(); } return arr.size()- iRet; } }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
