1

そのため、特定の単語の各文字の繰り返し回数をカウントするアルゴリズムを開発していました。私は a を使用してHashMapおり、各一意の文字をHashMapキーとして追加し、値は繰り返し回数です。ソリューションの実行時間と、問題を解決するためのより効率的な方法があるかどうかを知りたいです。

コードは次のとおりです。

public static void getCount(String name){
        public HashMap<String, Integer> names = new HashMap<String, Integer>() ;
        for(int i =0; i<name.length(); i++){

            if(names.containsKey(name.substring(i, i+1))){
                names.put(name.substring(i, i+1), names.get(name.substring(i, i+1)) +1);
            }
            else{
                names.put(name.substring(i, i+1), 1);
            }
        }

        Set<String> a = names.keySet();
        Iterator i = a.iterator();

        while(i.hasNext()){
            String t = (String) i.next();
            System.out.println(t + " Ocurred " + names.get(t) + " times");
        }
    }
4

4 に答える 4

2

アルゴリズムの時間計算量はですO(n)が、実装の一部を変更します。つまり、次のようになります。

  • +get()の代わりにシングルを使用する;containsKey()get()
  • charAt()代わりにを使用substring()すると、新しいStringオブジェクトが作成されます。
  • 全体ではなく、1つの文字だけを気にするので、Map<Character, Integer>代わりにを使用します。Map<String, Integer>String

言い換えると：

public static void getCount(String name) {
    Map<Character, Integer> names = new HashMap<Character, Integer>();
    for(int i = 0; i < name.length(); i++) {
        char c = name.charAt(i);
        Integer count = names.get(c);
        if (count == null) {
            count = 0;
        }
        names.put(c, count + 1);
    }
    Set<Character> a = names.keySet();
    for (Character t : a) {
        System.out.println(t + " Ocurred " + names.get(t) + " times");
    }
}
于 2012-08-30T03:00:50.810 に答える
1

あなたの解決策は、アルゴリズムの観点からは O(n) であり、これはすでに最適です (少なくとも、文字列全体の各文字を少なくとも 1 回は O(n) で検査する必要があります)。

ただし、一定のオーバーヘッドを減らすことで高速化できる方法がいくつかあります。

  • を使用しHashMap<Character,Integer>ます。文字は、長さ 1 の文字列よりもはるかに効率的です。
  • charAt(i)の代わりに使用しsubstring(i,i+1)ます。これにより、非常に役立つ新しい文字列の作成が回避されます。おそらく、あなたができる最大の単一の改善です。
  • 文字列が長くなる場合 (数千文字以上など) はint[]、HashMap ではなく配列を使用して個々の文字をカウントし、文字の ASCII 値を配列のインデックスとして使用することを検討してください。ただし、ストリングが短い場合、これは良い考えではありません。
于 2012-08-30T02:57:09.320 に答える
0

文字列 s="良い";

    //collect different unique characters 

    ArrayList<String> temp=new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        if(!temp.contains(""+c))
        {
            temp.add(""+s.charAt(i));

        }

    }

    System.out.println(temp);
    //get count of each occurrence in the string
    for (int i = 0; i < temp.size(); i++) {
        int count=0;
        for (int j = 0; j < s.length(); j++) {

            if(temp.get(i).equals(s.charAt(j)+"")){

                count++;
            }
        }
        System.out.println("Occurance of "+ temp.get(i) + " is "+ count+ " times" );
    }*/
于 2013-01-29T12:52:11.057 に答える
0

次のように、初期時間を変数に格納します。

long start = System.currentTimeMillis();

最後に、終了したら、現在の時刻から開始時刻を引いて出力します。

System.out.println((System.currentTimeMillis() - start) + "ms taken");

それを行うのにかかった時間を表示します。私が知る限り、それが最も効率的な方法ですが、別の良い方法があるかもしれません。また、個々の文字ごとに文字列ではなく文字を使用します (文字/文字は文字に最適なクラスであり、一連の文字には文字列です)、name.charAt(i)代わりname.substring(i, i+1)にハッシュマップを HashMap<Character, Integer> に変更します

于 2012-08-30T02:52:21.990 に答える