时间戳

首页 > 解决方案 > 我编写了一个带有双 for 循环的 anagrams finder - 如何提高此代码的效率？

java - 我编写了一个带有双 for 循环的 anagrams finder - 如何提高此代码的效率？

问题描述

针对 Hackerrank 问题：https ://www.hackerrank.com/challenges/ctci-making-anagrams/problem必须找到要从字符串中删除的字符数（作为整数）以使其成为字谜另一个字符串。

我已经完成了代码并且程序通过了测试，但我需要帮助来提高它的效率。我该如何思考如何提高以下代码的效率？

    import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Hackerank {

    // Complete the makeAnagram function below.
    static int makeAnagram(String a, String b) {
        int letterToRemoveCount = 0;
        Set<Character> characterMapA = new HashSet<>();
        Set<Character> characterMapB = new HashSet<>();

        for(int i = 0; i< a.length(); i++) {

            if (!characterMapA.contains(a.charAt(i))) {
                characterMapA.add(a.charAt(i));
                if ((countOccurences(a.charAt(i), a) - countOccurences(a.charAt(i), b)) != 0) {
                    letterToRemoveCount += Math.abs((countOccurences(a.charAt(i), a) - countOccurences(a.charAt(i), b)));
                }
            }
        }
        for (int j = 0; j<b.length(); j++){
            if (!characterMapB.contains(b.charAt(j)) && !characterMapA.contains(b.charAt(j))) {
                characterMapB.add(b.charAt(j));
                if ((countOccurences(b.charAt(j), a) - countOccurences(b.charAt(j), b)) != 0) {
                    letterToRemoveCount += Math.abs((countOccurences(b.charAt(j), a) - countOccurences(b.charAt(j), b)));
                }
            }
        }
        return letterToRemoveCount;

    }

    public static int countOccurences(char m, String s){
        int count = 0;
        for(int i = 0; i< s.length(); i++){
            if(s.charAt(i) == m){
                count++;
            }
        }
        return count;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        System.out.println(makeAnagram("fcrxzwscanmligyxyvym", "jxwtrhvujlmrpdoqbisbwhmgpmeoke"));
    }
}

标签： javastring

解决方案

优化的第一条规则：避免不必要的操作：

  • 就像打电话contains之前打电话一样add。

优化的第二条规则：如果你想要它更快，你最好依靠内存：

  • 不要使用相同的输入值多次调用相同的函数：最好只调用一次，将值存储在局部变量中，然后再使用它。
  • 此外，计算字符串中某个字符的出现次数效率不高（字符串越长，效率最低）：最好为每个字符串创建一个映射，将每个字符映射到出现次数。
  • Dave 关于如何优化此类地图的建议也很有趣。

推荐阅读