本文涉及的基础知识点
题目
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); }
