6

文字列内の最初の重複文字を検出するためのコードを以下に記述しました。

public static int detectDuplicate(String source) {
    boolean found = false;
    int index = -1;
    final long start = System.currentTimeMillis();
    final int length = source.length();
    for(int outerIndex = 0; outerIndex < length && !found; outerIndex++) {
        boolean shiftPointer = false;
        for(int innerIndex = outerIndex + 1; innerIndex < length && !shiftPointer; innerIndex++ ) {
            if ( source.charAt(outerIndex) == source.charAt(innerIndex)) {
                found = true;
                index = outerIndex;
            } else {
                shiftPointer = true;
            }
        }
    }
    System.out.println("Time taken --> " + (System.currentTimeMillis() - start) + " ms. for string of length --> " + source.length());
    return index;
}

次の 2 つの点で助けが必要です。

  • このアルゴリズムの最悪の場合の複雑さは? - 私の理解は O(n) です。
  • これを行うのが最善の方法ですか？誰かがより良い解決策を提供できますか (もしあれば)?

ありがとう、NN

4

7 に答える 7

13

他の人が述べたように、アルゴリズムは O(n^2) です。HashSet#add は一定時間で実行されるため (ハッシュ関数はバケット間で要素を適切に分散させます)、O(N) アルゴリズムを次に示します。サイズ変更/再ハッシュを避けるために、最初はハッシュセットのサイズを最大サイズに設定していることに注意してください。

public static int findDuplicate(String s) {
    char[] chars = s.toCharArray();
    Set<Character> uniqueChars = new HashSet<Character> (chars.length, 1);
    for (int i = 0; i < chars.length; i++) {
        if (!uniqueChars.add(chars[i])) return i;
    }
    return -1;
}

注: これは、最初の重複のインデックス (つまり、前の文字の重複である最初の文字のインデックス) を返します。その文字の最初の出現のインデックスを返すには、インデックスを a に格納する必要がありますMap<Character, Integer>(Map#putこの場合も O(1) です)。

public static int findDuplicate(String s) {
    char[] chars = s.toCharArray();
    Map<Character, Integer> uniqueChars = new HashMap<Character, Integer> (chars.length, 1);
    for (int i = 0; i < chars.length; i++) {
        Integer previousIndex = uniqueChars.put(chars[i], i);
        if (previousIndex != null) {
            return previousIndex;
        }
    }
    return -1;
}
于 2012-09-06T17:14:54.383 に答える
1

これは O(n) ではなく O(n**2) です。ケースを考えてみましょうabcdefghijklmnopqrstuvwxyzz。outerIndexプロシージャが終了する前に 0 から 25 の範囲になり、増分するたびに 26 から 26 のinnerIndex範囲になりますouterIndex。

O(n) に到達するには、リストを 1 回パスし、各位置で O(1) の作業を行う必要があります。各位置で行う作業は、キャラクターが以前に見られたかどうか (また、そうであればどこで) を確認することなので、O(1) マップの実装が必要であることを意味します。ハッシュテーブルがそれを提供します。文字コードでインデックス付けされた配列も同様です。

assyliasは hashingでそれを行う方法を示しているので、配列でそれを行う方法は次のとおりです(本当に笑いのために):

public static int detectDuplicate(String source) {
    int[] firstOccurrence = new int[1 << Character.SIZE];
    Arrays.fill(firstOccurrence, -1);
    for (int i = 0; i < source.length(); i++) {
        char ch = source.charAt(i);
        if (firstOccurrence[ch] != -1) return firstOccurrence[ch];
        else firstOccurrence[ch] = i;
    }
    return -1;
}
于 2012-09-06T17:11:42.220 に答える
1

複雑さはおおよそ次のとおりですO(M^2)。ここMで、 は文字列の長さと可能な文字セットのサイズの間の最小値Kです。

O(M)すべてのユニークなキャラクターに最初に遭遇する位置をO(K)記憶するだけで、記憶にとどめることができます。

于 2012-09-06T17:12:12.140 に答える
0

わかりました、以下のロジックを見つけて に減らしO(N^2)ましたO(N)。

public static int detectDuplicate(String source) {
    int index = -1;
    boolean found = false;
    final long start = System.currentTimeMillis();

    for(int i = 1; i <= source.length() && !found; i++) {
        if(source.charAt(i) == source.charAt(i-1)) {
            index = (i - 1);
            found = true;
        }
    }

    System.out.println("Time taken --> " + (System.currentTimeMillis() - start) + " ms. for string of length --> " + source.length());
    return index;
}

これは、2 つのネストされたループを持つ以前のアルゴリズムよりもパフォーマンスが向上していることも示しています。これは、重複文字が最後に存在する130ms.文字から最初の重複文字を検出するために必要です。63million

これが最善の解決策であるかどうかはわかりません。誰かがより良いものを見つけたら、それを共有してください。

ありがとう、

NN

于 2012-09-08T04:01:29.990 に答える
0

あなたのアルゴリズムを大幅に改善できます。次のように行う必要があります。

StringBuffer source ...
char charLast = source.charAt( source.len()-1 );
int xLastChar = source.len()-1;
source.setCharAt( xLastChar, source.charAt( xLastChar - 1 ) );
int i = 1;
while( true ){
    if( source.charAt(i) == source.charAt(i-1) ) break;
    i += 1;
}
source.setCharAt( xLastChar, charLast );
if( i == xLastChar && source.charAt( xLastChar-1 ) != charLast ) return -1;
return i;

大きな文字列の場合、このアルゴリズムはおそらくあなたのアルゴリズムの 2 倍高速です。

于 2012-10-25T17:33:55.877 に答える
-1

O(1)アルゴリズム

2つのネストされたループがあるため、ソリューションはO（n ^ 2）です。

これを行うための最速のアルゴリズムはO(1)（定数時間）です：

public static int detectDuplicate(String source) {
    boolean[] foundChars = new boolean[Character.MAX_VALUE+1];
    for(int i = 0; i < source.length(); i++) {
        if(i >= Character.MAX_VALUE) return Character.MAX_VALUE;
        char currentChar = source.charAt(i);
        if(foundChars[currentChar]) return i;
        foundChars[currentChar] = true;
    }
    return -1;
}

ただし、これは大きな意味でのみ高速です。

于 2012-09-06T17:11:09.567 に答える