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

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

本文涉及的基础知识点

二分查找算法合集

题目

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);
}


相关文章
|
5天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
24 2
|
13天前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
11天前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
18天前
|
算法 安全 C++
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
38 4
|
3月前
|
程序员 C++ 容器
在 C++中,realloc 函数返回 NULL 时,需要手动释放原来的内存吗?
在 C++ 中,当 realloc 函数返回 NULL 时,表示内存重新分配失败,但原内存块仍然有效,因此需要手动释放原来的内存,以避免内存泄漏。
|
3月前
|
存储 前端开发 C++
C++ 多线程之带返回值的线程处理函数
这篇文章介绍了在C++中使用`async`函数、`packaged_task`和`promise`三种方法来创建带返回值的线程处理函数。
116 6
|
3月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
876 0
高精度算法(加、减、乘、除,使用c++实现)
|
3月前
|
C++
C++ 多线程之线程管理函数
这篇文章介绍了C++中多线程编程的几个关键函数,包括获取线程ID的`get_id()`,延时函数`sleep_for()`,线程让步函数`yield()`,以及阻塞线程直到指定时间的`sleep_until()`。
52 0
|
3月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
62 0
|
7天前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。