java - 从第二个字符串中删除第一个字符串中存在的字符

Question

我编写了一个程序来删除第二个字符串中存在于第一个字符串中的字符。复杂度为 BigO(n^2)。能否进一步降低复杂度？

public class Tmp {

    public static void main(String[] args) {
        String s = "halloween";
        String s1 = "halcyon";
        char[] ss = s.toCharArray();
        char[] ss1 = s1.toCharArray();

        for(int i=0;i<ss.length;i++){
          for(int j=0;j<ss1.length;j++){
                if(ss1[j] == ss[i]){
                    ss1[j] = 'x'; //Replace the common char with x
                }
            }
         }
        System.out.println(Arrays.toString(ss1));
    }
}

输出

 [x, x, x, c, y, x, x]

Answer 1

1. 将第一个字符串转换为 Map。 O(N)
2. 遍历其他字符串并检查步骤 1 中的字符是否存在于 Map 中。O(N) + O(1)

总时间复杂度 = O(N)

这里你有额外的空间复杂度来存储 MAP。