C++二分算法:找到最接近目标值的函数值

news/2024/5/20 21:39:01

本文涉及的基础知识点

二分查找算法合集

题目

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(logn+logm)) 约O(3e7) 处于超时边缘。

核心代码

class Solution {
public:int closestToTarget(vector<int>& arr, int target) {m_c = arr.size();const int iBitNum = 21;vector<vector<int>> 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++){set<int> 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);}}vector<int> 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 vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}
}int main()
{vector<int> 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(vector<int>& arr, int target) {m_c = arr.size();const int iBitNum = 21;vector<int> vPre(iBitNum, -1);multiset<int> 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;}vector<int> 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,l+1,r)。
令iMax=max(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(vector<int>& arr, int target) {m_c = arr.size();	set<int> setPre = { arr.back() };int iRet = abs(arr.back() - target);for (int left = m_c - 1-1; left >= 0; left--){set<int> 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(vector<int>& arr, int target) {m_c = arr.size();	vector<int> vPre = { arr.back() };int iRet = abs(arr.back() - target);for (int left = m_c - 1-1; left >= 0; left--){vector<int> 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(pr&a);
queNear.push(abs((pr&a)-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

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

https://www.xjx100.cn/news/3090465.html

相关文章

《崩坏:星穹铁道》1.5仙舟罗浮-绥园全宝箱攻略

大家好&#xff0c;我是闲游盒小盒子&#xff0c;本篇来说下崩铁1.5版本仙舟罗浮-绥园的全宝箱攻略&#xff0c;共有19个宝箱加1个扑满&#xff1b;做完间章可获取前14个普通宝箱加2个精英怪宝箱&#xff0c;以及1个扑满&#xff1b;完成《狐斋志异》全任务可获得另外3个宝箱。…

Flink Operator 使用指南 之 Flink Operator安装

介绍 Flink Kubernetes Operator 充当控制平面来管理 Apache Flink 应用程序的完整部署生命周期。尽管 Flink 的Native Kubernetes 集成已经允许用户在运行的 Kubernetes(k8s) 集群上直接部署 Flink 应用程序,但自定义资源和Operator Pattern 也已成为 Kubernetes 原生部署体…

机器学习-笔记

绪论 参考期刊 ICCV 偏向视觉CVPR 偏向MLIAAA AI原理ICML 参考链接 CSDN 机器学习知识点全面总结 课堂内容学习-0912-N1 对于特征提取&#xff0c;简而言之就是同类聚得紧&#xff0c;异类分得开&#xff1b;   detection研究的是样本二分类问题&#xff0c;即分为正样本…

leetcode做题笔记242. 有效的字母异位词

给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意&#xff1a;若 s 和 t 中每个字符出现的次数都相同&#xff0c;则称 s 和 t 互为字母异位词。 示例 1: 输入: s "anagram", t "nagaram" 输出: true示例 2: 输…

C++二分查找算法:132模式枚举3简洁版

本文涉及的基础知识点 二分查找算法合集 本题不同解法 包括题目及代码C二分查找算法&#xff1a;132 模式解法一枚举3C二分查找算法&#xff1a;132 模式解法二枚举2代码简洁C二分查找算法&#xff1a;132 模式解法三枚举1性能最佳C单调向量算法&#xff1a;132 模式解法三枚…

使用Python实现几种底层技术的数据结构

使用Python实现几种底层技术的数据结构 数据结构(data structure)是带有结构特性的数据元素的集合&#xff0c;它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系&#xff0c;并对这种结构定义相适应的运算&#xff0c;设计出相应的算法&#xff0c;并确保经过这…

Thinkphp-商城项目之oss文件上传及web端直传

4.3头像上传 一般商城网站都会把文件上传到第三方云&#xff0c;例如阿里云(oss)&#xff0c;腾讯云(cos)&#xff0c;当然如果公司有足够的实力&#xff0c;可以自己部署一台文件服务器&#xff0c;用于文件的保存。 头像上传一般是用户在用户中心上传的&#xff0c;后台管理…

从0开始学习JavaScript--JavaScript使用Promise

JavaScript中的异步编程一直是开发中的重要话题。传统的回调函数带来了回调地狱和代码可读性的问题。为了解决这些问题&#xff0c;ES6引入了Promise&#xff0c;一种更现代、更灵活的异步编程解决方案。本文将深入探讨JavaScript中如何使用Promise&#xff0c;通过丰富的示例代…