欢迎光临散文网 会员登陆 & 注册

二分/双指针

2022-05-27 21:24 作者:剑离我离  | 我要投稿

单词距离

二分

对于进阶部分内容,开始的想法是用一个map记录所有的元素对应的所有下标,再用二分的形式,找到每一个元素的每个下标最佳位置;时间复杂度o(nlogn) 不是最优做法;主要是这个过程运用二分所出现的问题解决;

在这样找的二分中,必定是找不到相等值的,这样,最优值自然会落在二分出来的l和r附近;

但这个值可能不是l这个值,而是,l-1;这是用例子分析出来的;

例如 target = 3 ; 在 1 5 8 三个元素的数组里找,初始 l=0,r=3; mid = 1; 即找到5,然后 r = 1;mid=0; 出循环的时候 l = mid+1 ;(理应没有+1) ,这就造成了数据误差,因此在实际更新min值的时候,要对l和l-1的值都要进行判定是否满足;

简单模拟(双指针)

对words进行遍历,使用两个指针 p 和 q 分别记录最近的两个关键字的位置,并维护最小更新距离


二分/双指针的评论 (共 条)

分享到微博请遵守国家法律