算法题 字符的最短距离

字符的最短距离

问题描述

给你一个字符串s和一个字符c，其中c在s中至少出现一次。

返回一个整数数组answer，其中answer[i]是字符串s中下标i处的字符到最近的字符c的最短距离。

两个下标i和j之间的距离为abs(i - j)。

示例：

输入: s = "loveleetcode", c = "e" 输出: [3,2,1,0,1,0,0,1,2,2,1,0] 解释: 字符 'e' 在下标 3、5、6、11 处出现。 对于下标 0，最近的 'e' 在下标 3，距离为 |0-3| = 3。 对于下标 1，最近的 'e' 在下标 3，距离为 |1-3| = 2。 ...

算法思路

核心：

1. 最近距离：对于任意位置 i，最近的字符 c 要么在 i 的左边，要么在 i 的右边
2. 两次遍历：
   • 第一次从左到右：记录每个位置到左边最近 c 的距离
   • 第二次从右到左：记录每个位置到右边最近 c 的距离
   • 取两次遍历结果的最小值

方法：

• 两次遍历：时间复杂度 O(n)，空间复杂度 O(1)
• 预处理位置：先找到所有 c 的位置，然后对每个位置二分查找最近的 c
• 暴力：对每个位置遍历整个字符串找最近的 c（效率低）

代码实现

方法一：两次遍历

classSolution{/** * 使用两次遍历计算每个字符到最近目标字符的最短距离 * * @param s 输入字符串 * @param c 目标字符 * @return 每个位置到最近c的最短距离数组 */publicint[]shortestToChar(Strings,charc){intn=s.length();int[]result=newint[n];// 初始化为一个很大的值（大于可能的最大距离）// 最大距离不会超过n，所以用n作为初始值for(inti=0;i<n;i++){result[i]=n;}// 第一次遍历：从左到右，计算到左边最近c的距离intprev=-n;// 记录上一个c的位置，初始化为-n确保第一次更新for(inti=0;i<n;i++){if(s.charAt(i)==c){prev=i;}result[i]=Math.min(result[i],i-prev);}// 第二次遍历：从右到左，计算到右边最近c的距离prev=2*n;// 记录下一个c的位置，初始化为2*n确保第一次更新for(inti=n-1;i>=0;i--){if(s.charAt(i)==c){prev=i;}result[i]=Math.min(result[i],prev-i);}returnresult;}}

方法二：预处理位置 + 二分查找

importjava.util.*;classSolution{/** * 先预处理所有目标字符的位置，然后对每个位置二分查找最近的位置 */publicint[]shortestToChar(Strings,charc){// 预处理：找到所有c的位置List<Integer>positions=newArrayList<>();for(inti=0;i<s.length();i++){if(s.charAt(i)==c){positions.add(i);}}int[]result=newint[s.length()];// 对每个位置，找到最近的cfor(inti=0;i<s.length();i++){result[i]=findMinDistance(positions,i);}returnresult;}/** * 在有序位置列表中找到距离target最近的位置 */privateintfindMinDistance(List<Integer>positions,inttarget){// 二分查找插入位置intleft=0,right=positions.size();while(left<right){intmid=left+(right-left)/2;if(positions.get(mid)<target){left=mid+1;}else{right=mid;}}intminDist=Integer.MAX_VALUE;// 检查left位置（第一个>=target的位置）if(left<positions.size()){minDist=Math.min(minDist,positions.get(left)-target);}// 检查left-1位置（最后一个<target的位置）if(left>0){minDist=Math.min(minDist,target-positions.get(left-1));}returnminDist;}}

方法三：暴力

classSolution{/** * 暴力：对每个位置遍历整个字符串 */publicint[]shortestToChar(Strings,charc){intn=s.length();int[]result=newint[n];for(inti=0;i<n;i++){intminDist=n;// 最大可能距离for(intj=0;j<n;j++){if(s.charAt(j)==c){minDist=Math.min(minDist,Math.abs(i-j));}}result[i]=minDist;}returnresult;}}

算法分析

• 时间复杂度：

  • 两次遍历：O(n) - 三次线性扫描（初始化+两次遍历）
  • 预处理+二分查找：O(n log k) - k是字符c的出现次数
  • 暴力：O(n²)

• 空间复杂度：

  • 两次遍历：O(1) - 只使用常数额外空间
  • 预处理+二分查找：O(k) - 存储c的位置
  • 暴力：O(1)

算法过程

1：s = “loveleetcode”, c = “e”

字符e的位置：[3, 5, 6, 11]

两次遍历：

第一次遍历（左到右）：

• i=0: prev=-12, dist=0-(-12)=12
• i=1: prev=-12, dist=13
• i=2: prev=-12, dist=14
• i=3: s[3]==‘e’, prev=3, dist=0
• i=4: prev=3, dist=1
• i=5: s[5]==‘e’, prev=5, dist=0
• i=6: s[6]==‘e’, prev=6, dist=0
• i=7: prev=6, dist=1
• …继续到i=11

中间结果：[12,13,14,0,1,0,0,1,2,3,4,0]

第二次遍历（右到左）：

• i=11: s[11]==‘e’, prev=11, dist=min(0, 0)=0
• i=10: prev=11, dist=min(4, 1)=1
• i=9: prev=11, dist=min(3, 2)=2
• i=8: prev=11, dist=min(2, 3)=2
• i=7: prev=11, dist=min(1, 4)=1
• i=6: s[6]==‘e’, prev=6, dist=min(0, 0)=0
• i=5: s[5]==‘e’, prev=5, dist=min(0, 0)=0
• i=4: prev=5, dist=min(1, 1)=1
• i=3: s[3]==‘e’, prev=3, dist=min(0, 0)=0
• i=2: prev=3, dist=min(14, 1)=1
• i=1: prev=3, dist=min(13, 2)=2
• i=0: prev=3, dist=min(12, 3)=3

最终结果：[3,2,1,0,1,0,0,1,2,2,1,0]

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]result1=solution.shortestToChar("loveleetcode",'e');System.out.println("Test 1: "+Arrays.toString(result1));// [3,2,1,0,1,0,0,1,2,2,1,0]// 测试用例2：目标字符在开头int[]result2=solution.shortestToChar("aaab",'b');System.out.println("Test 2: "+Arrays.toString(result2));// [3,2,1,0]// 测试用例3：目标字符在结尾int[]result3=solution.shortestToChar("baaa",'b');System.out.println("Test 3: "+Arrays.toString(result3));// [0,1,2,3]// 测试用例4：所有字符都是目标字符int[]result4=solution.shortestToChar("eeee",'e');System.out.println("Test 4: "+Arrays.toString(result4));// [0,0,0,0]// 测试用例5：只有一个目标字符int[]result5=solution.shortestToChar("abcdefg",'d');System.out.println("Test 5: "+Arrays.toString(result5));// [3,2,1,0,1,2,3]// 测试用例6：单字符字符串int[]result6=solution.shortestToChar("a",'a');System.out.println("Test 6: "+Arrays.toString(result6));// [0]// 测试用例7：两个字符int[]result7=solution.shortestToChar("ab",'b');System.out.println("Test 7: "+Arrays.toString(result7));// [1,0]// 测试用例8：目标字符多次出现int[]result8=solution.shortestToChar("abccba",'c');System.out.println("Test 8: "+Arrays.toString(result8));// [2,1,0,0,1,2]// 测试用例9：长字符串int[]result9=solution.shortestToChar("abcdefghijklmnopqrstuvwxyz",'m');System.out.println("Test 9: "+Arrays.toString(result9));// [12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13]// 测试用例10：目标字符在中间int[]result10=solution.shortestToChar("abcde",'c');System.out.println("Test 10: "+Arrays.toString(result10));// [2,1,0,1,2]}

关键点

1. 两次遍历：

   • 单次遍历无法同时考虑左右两边的最近字符
   • 两次遍历分别处理左边界和右边界情况

2. 初始化：

   • 使用足够大的初始值确保正确更新
   • 避免使用Integer.MAX_VALUE防止溢出

3. 距离计算：

   • 左到右：i - prev（prev ≤ i）
   • 右到左：prev - i（prev ≥ i）
   • 保证距离为正数

4. 边界处理：

   • 字符串开头：只有右边的字符可选
   • 字符串结尾：只有左边的字符可选

常见问题

1. 为什么不能用一次遍历？
   • 一次遍历只能知道已遍历部分的信息
   • 无法预知右边是否有更近的字符