二分/双指针
单词距离
二分
对于进阶部分内容,开始的想法是用一个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 分别记录最近的两个关键字的位置,并维护最小更新距离