做网站推广优化哪家好,沐风+wordpress+主题,400建筑人才网,网站优化方法本文涉及的基础知识点
二分查找算法合集
题目
Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target #xff0c;他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。 请你返回 |func(arr, l, r) - target| 的最小值。 请注意#xff0c…本文涉及的基础知识点
二分查找算法合集
题目
Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target 他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。 请你返回 |func(arr, l, r) - target| 的最小值。 请注意 func 的输入参数 l 和 r 需要满足 0 l, r arr.length 。 示例 1 输入arr [9,12,3,7,15], target 5 输出2 解释所有可能的 [l,r] 数对包括 [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]] Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0] 。最接近 5 的值是 7 和 3所以最小差值为 2 。 示例 2 输入arr [1000000,1000000,1000000], target 1 输出999999 解释Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 所以最小差值为 999999 。 示例 3 输入arr [1,2,4,8,16], target 0 输出0 参数范围 1 arr.length 10^5 1 arr[i] 10^6 0 target 10^7
方法一超时
按二进制的位讨论
对任意一个二进制位从左到右出现第一个0之前是1之后是0。我们用vIndexs记录各二进制位0的索引。 两层循环第一层循环枚举起始l第二层循环枚举各位。只需要考虑有二进位第一个变成0的位。
时间复杂度
O(nlogmax(lognlogm)) 约O(3e7) 处于超时边缘。
核心代码
class Solution {
public:int closestToTarget(vectorint arr, int target) {m_c arr.size();const int iBitNum 21;vectorvectorint vIndexs(iBitNum);for (int i 0; i m_c; i){for (int j 0; j iBitNum; j){if (arr[i] (1 j)){continue;}vIndexs[j].emplace_back(i);}}int iRet INT_MAX;for (int l 0; l m_c; l){setint setIndexs ;for (int j 0; j iBitNum; j){auto it std::lower_bound(vIndexs[j].begin(), vIndexs[j].end(), l);if (vIndexs[j].end() ! it){setIndexs.emplace(*it);}}vectorint vValue { arr[l] };for (const auto index : setIndexs){vValue.emplace_back(vValue.back() arr[index]);}for (const auto value : vValue){iRet min(iRet, abs(value - target));}}return iRet;}int m_c;
};测试用例
template class T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}template class T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}
}int main()
{vectorint arr;int target;int res;{Solution slu; arr { 9, 12, 3, 7, 15 };int target 5;res slu.closestToTarget(arr, target);Assert(2, res);}{Solution slu;arr { 1000000,1000000,1000000 };int target 1;res slu.closestToTarget(arr, target);Assert(999999, res);}{Solution slu;arr { 1,2,4,8,16 };int target 0;res slu.closestToTarget(arr, target);Assert(0, res);}//CConsole::Out(res);}方法二超时
分析
从右向左枚举左边缘setIndexs 记录各位为0的最小索引vPre记录本位的上一个索引方便删除。
时间复杂度
O(nlogmax(loglogmax)nlogmax)
核心代码
class Solution {
public:int closestToTarget(vectorint arr, int target) {m_c arr.size();const int iBitNum 21;vectorint vPre(iBitNum, -1);multisetint setIndexs;int iRet INT_MAX;for (int left m_c - 1; left 0; left--){for (int iBit 0; iBit iBitNum; iBit){if (arr[left] (1 iBit)){continue;}if (-1 ! vPre[iBit]){setIndexs.erase(setIndexs.find(vPre[iBit]));}setIndexs.emplace(left);vPre[iBit] left;}vectorint vValue { arr[left] };for (const auto index : setIndexs){vValue.emplace_back(vValue.back() arr[index]);}for (const auto value : vValue){iRet min(iRet, abs(value - target));}}return iRet;}int m_c;
};方法三
分析
func(arr,l,r)等于arr[l]func(arr,l1,r)。 令iMaxmax(nums[i]) func(arr,l,x) x取值范围[l,n) 最多只有log(iMax)种可能。nums[i]最多有log(iMax)个二进制位为1,and只会将1变成0不会将0变成1。所以1只会不断减少最坏的情况下每次减少一个1共减少log(iMax)次。
时间复杂度
O(nlogmaxloglogmax)。稳定能过。
class Solution {
public:int closestToTarget(vectorint arr, int target) {m_c arr.size(); setint setPre { arr.back() };int iRet abs(arr.back() - target);for (int left m_c - 1-1; left 0; left--){setint dp { arr[left] };for (const auto pr : setPre){dp.emplace(pr arr[left]);}setPre.swap(dp);for (const auto pr : setPre){iRet min(iRet, abs(pr - target));}}return iRet;}int m_c;
};方法四
分析
dp本来就是降序所有用向量也可以判断是否重复换成向量速度再次提升。理论上速度可以提升几倍实际提升50%左右。
时间复杂度
O(nlogmax)。
class Solution {
public:int closestToTarget(vectorint arr, int target) {m_c arr.size(); vectorint vPre { arr.back() };int iRet abs(arr.back() - target);for (int left m_c - 1-1; left 0; left--){vectorint dp { arr[left] };for (const auto pr : vPre){const int iNew pr arr[left];if (dp.back() ! iNew){dp.emplace_back(iNew);}}vPre.swap(dp);for (const auto pr : vPre){iRet min(iRet, abs(pr - target));}}return iRet;}int m_c;
};2023年3月第一版
class Solution { public: int closestToTarget(vector arr, int target) { std::set pre; std::priority_queue queNear; for (const auto a : arr) { std::set dp; for (const auto pr : pre) { dp.insert(pra); queNear.push(abs((pra)-target)); if (queNear.size() 1) { queNear.pop(); } } dp.insert(a); queNear.push(abs(a-target)); if (queNear.size() 1) { queNear.pop(); } pre.swap(dp); } return queNear.top(); } };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。墨子曰事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
