当前位置: 首页 > article >正文

(二分 数学推导区间 两个数组的距离值)leetcode 1385

数学推导:

设arr1[i]=x 则|x-arr2[j]|<=d

也就是当arr2[j]属于[x-d,x+d]的范围的时候,就不满足条件

执行过程:

我们把arr2排序

使用lower_bound找到第一个大于等于x-d的数为t

再判断是否位于end()或者*t>x+d

而这个数t有三种可能

1.刚好等于x-d不满足条件

2.大于x-d但是小于等于x+d 不满足条件

3.大于x+d 满足条件

那arr2中小于t的值呢,因为t>=x-d 所以arr2<t的值一定arr[j]<x-d满足区间条件

为什么不选upper_bound?

答:当x-d存在于arr2 但是t不等于x-2导致判断出错

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(),arr2.end());
        int ans=0;
        for(auto x:arr1)
        {
           auto t=ranges::lower_bound(arr2,x-d);
           if(t==arr2.end()||*t>x+d)
           ans++;
        }
        return ans;
    }
};


http://www.kler.cn/a/580834.html

相关文章:

  • 【第21节】C++设计模式(行为模式)-Chain of Responsibility(责任链)模式
  • Redis7——进阶篇(五)
  • Consensus 大会全观察:政策、生态与技术交汇,香港能否抢占 Web3 先机?
  • 【网络编程】WSAAsyncSelect 模型
  • redis 用来实现排行榜的功能
  • Qt 中实现自定义控件子类化
  • scala传递匿名函数简化的原则
  • Android 低功率蓝牙之BluetoothGattCharacteristic详解
  • linux下文件读写操作
  • 探索CAMEL:揭开多智能体系统的神秘面纱
  • upload-labs(1-20)详解(专业版)
  • JVM参数调整
  • Linux——基础IO【3万字大章】
  • 第四次CCF-CSP认证(含C++源码)
  • 构建服务器--在线单词查询
  • Ubuntu 22.04 升级到 Ubuntu 24.04 全流程指南
  • tcc编译器教程6 进一步学习编译gmake源代码
  • Unity2017打包出来后的场景一片红
  • P8630 [蓝桥杯 2015 国 B] 密文搜索--map、substr
  • 大型语言模型为何看不懂电路图:局限性分析