0

私はたくさんの列を持つ本当に大きなフィードファイルを持っています。私は文字列で列の1つを表します、そして私はこれらの文字列をチェックしたいと思います...

これらの文字列値が（列に）あることを確認しましょう。フィードは明らかに機能的です:)：

"Gia Joe Black Viper"
"Street Fighter...Ken"
"Mortal Kombat, Scorpion"
"Gia Joe Desert Fox"
"Mortal Kombat, Sub Zero"
"Street Fighter...Ryu"

文字列内の一致を見つけたいのですが...タスクを単純化するには、別の文字列内の文字列サブ文字列の1つを見つけて、これらのサブ文字列をHashSetに収集します...

したがって、基本的に結果タグは次のようになります。

Gi Joe 
Mortal Kombat 
Street Fighter

アルゴリズムをテストするための簡単なコードを記述しますが、このタスクの時間計算量を最小限に抑えたいので、スペースの複雑さは時間ほど重要ではありません...（10.000行のようなフィードを考えることができるので、時間計算量が低い）私のコードの下で見つけて読むことができます：

    String[] stringArray = new String[6];
        stringArray[0] = "Mortal Kombat - Scorpion";
        stringArray[1] = "Street Fighter - Ken";
        stringArray[2] = "Mortal Kombat - Scorpion";
        stringArray[3] = "Gi Joe - Desert Fox";
        stringArray[4] = "Gi Joe - Desert Dog";
        stringArray[5] = "Street Fighter - Ryu";

        HashSet<String> commonStrings = new HashSet();

        for (int i = 0; i < stringArray.length; i++) {
            String[] splittedString = stringArray[i].split("[ ]");
            System.out.println("i"+i);
            for (int j = 0; j < stringArray.length; j++) {
                System.out.println("j"+j);
                String matchable = "";
                for (int k = 0; k < splittedString.length; k++) {
                    System.out.println("k"+k);
                    if(k==0)matchable=matchable;
                    else {matchable = matchable + " " + splittedString[k];}
                    if(j!=i){
                        System.out.println("StringArray["+j+"]("+stringArray[j]+")index.of("+matchable+")"+"is"+matchable.indexOf(stringArray[j]));
                        if (stringArray[j].indexOf(matchable) > 0) {
                            commonStrings.add(matchable);
                        }
                    }
                }
            }

私のコードをより良くするための提案はありがたいです、ありがとう！

4

2 に答える 2

2

複雑さは2次式であり、次のようなハッシュマップを使用することでO（n）にすることができます。

Map<String, Integer> cout = new HashMap<String, Integer>();

for (String line : StringArray) {
  for (String s : line.split("-")) {
     Integer currentCount = counts.get(s);
     if (currentCount == null)
       counts.put(s, 1);
     else
       counts.put(s, currentCount + 1);
  }
}
//Look in currentCount all keys with a value larger than 1.

これは、ステートメントを改善することで最適化できます（ただし、複雑さは軽減されませんelse）。

于 2012-08-22T12:49:09.760 に答える
1

このような並べ替えられたリストを繰り返すよりも、単語を分割して並べ替えることができます。結果は同じであるはずです。もちろん、これは単語全体をチェックするための解決策です。並べ替えの代わりに、専用のデータ構造を使用できます。

于 2012-08-22T12:50:16.783 に答える