> 文档中心 > Day【2】字符的最短距离

Day【2】字符的最短距离

原题链接

算法一

  1. 时间复杂度为:O(n ^ 2)
  2. 思路:暴力枚举,对于每个位置都向左右两个方向进行搜索,判断每个位置上的字符是否是c,如果是,进行相应的计算即可
class Solution {    public int[] shortestToChar(String s, char c) { int n = s.length(); int[] ans = new int[n]; for(int i = 0; i < n; i++){     int left = i;     int right = i+1;     int res  = Integer.MAX_VALUE;     while(left >= 0) {  if(s.charAt(left) == c) res = Math.min(res, Math.abs(i - left));  left --;     }     while(right < n) {  if(s.charAt(right) == c) res = Math.min(res, Math.abs(i - right));  right ++;     }     ans[i] = res; } return ans;    }}

算法二

  • 时间复杂度:O(n)
  • 思路: 在算法一中,对于每个位置我们都要向左 和向右搜索距离这个位置最近的c,这种算法的时间复杂度很高,并且在做很多无用功。对于每个位置,我们如果说知道了他的前一位,距离最近的c 的位置,我们就不需要每个位置都进行枚举
  • 通过这种思想,我们只需要向左扫一遍,记住每个位置上,左边距离它最近的c的距离;在向右扫一遍,记住每个位置上,右边距离它最近的c的位置,就行。
  • 这里pre 除以2 的目的是为了,防止越界
class Solution {    public int[] shortestToChar(String s, char c) { int n = s.length(); int[] ans = new int[n]; int pre = Integer.MIN_VALUE / 2; for(int i = 0; i < n; i++) {     if(s.charAt(i) == c) {  pre = i;     }     ans[i] = i - pre; } pre = Integer.MAX_VALUE / 2; for(int i = n -1; i >= 0; i--) {     if(s.charAt(i) == c) {  pre = i;     }     ans[i] = Math.min(ans[i],pre- i); } return ans;    }}