方法二：超时
分析
从右向左枚举左边缘，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
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨子曰：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
