配列と文字列コードをクラックするインタビュー6th ed Soln 1.1

Question

私は空き時間にコードインタビューをクラッキングしています。 質問は次のように述べています。ユニーク：文字列がすべて一意の文字を持つかどうかを判断するアルゴリズムを実装します。追加のデータ構造を使用できない場合はどうなりますか？

Iが見つかった溶液である：https://github.com/careercup/CtCI-6th-Edition-cpp/blob/master/Ch%201.Arrays%20And%20Strings/1.Is%20Unique/1.%20Is_unique.cpp

私の実装では、次のとおり

BOOL UniqueCharsHash（文字列ワード）{

map<char, bool> uniqueChar; //keyType, valueType 

for (int i = 0; i < word.length(); i++) { 
    char letter = tolower(word[i]); 
    if (!uniqueChar[letter]) { 
     uniqueChar[letter] = true; 
    } else { 
     return false; 
    } 
} 
return true; 

}

//O(n^2) run time using a two loops (1 outer and 1 inner) 
bool UniqueCharNoDS(string word) { 
for (int i = 0; i < word.length() - 1; i++) { 
    for (int j = i + 1; j < word.length(); j++) { 
     if (word[i] == word[j]) { 
      return false; 
     } 
    } 
} 

return true; 

}

それは述べブックのヒント部分で：

1. ハッシュテーブル
2. を試すビットベクトルは
3. 役に立つかもしれない、あなたはO（Nlogn）時間

でそれを解決することができます

私は3つの方法で、NlogN時間のいずれかが表示されるのだろうか？

Answer 1

よく指摘されているように、この質問はO（1）で解決できます。一意の文字で構成された最長の文字列は256文字です。

アルゴリズムが257番目の文字に当たると、/を停止して「いいえ」と報告することができます。

プレフィックス内の各文字をそのポイントまで検索する単純なアルゴリズムを使用しても、制限に達する前に最大255×128の比較があります。 （アルゴリズムの調整は必要ありませんが、257番目の文字がある場合は「いいえ」と報告する必要があります）

Answer 2

以下のコードでは、文字列にすべて一意の文字が含まれているかどうかが判断されます。
時間複雑 - > O（N）

final static int LETTERS_LEN = 256; 
public static boolean isUnique(String str){ 

    int[] letters = new int[LETTERS_LEN]; 

    for (int i = 0; i < str.length(); i++) { 
     letters[str.charAt(i)]++; 
    } 

    for (int i = 0; i < LETTERS_LEN; i++) { 
     if (letters[i] > 1) { 
      return false; 
     } 
    } 
    return true; 
} 

Answer 3

このコードは、O（NlogN）の時間でそれを解決するには、ソート

boolean isUnique(char[] arr){ 
     return sort(arr,0,arr.length-1); 
} 

// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
boolean merge(char arr[], int l, int m, int r) 
{ 
    // Find sizes of two subarrays to be merged 
    int n1 = m - l + 1; 
    int n2 = r - m; 

    /* Create temp arrays */ 
    char L[] = new char [n1]; 
    char R[] = new char [n2]; 

    /*Copy data to temp arrays*/ 
    for (int i=0; i<n1; ++i) 
     L[i] = arr[l + i]; 
    for (int j=0; j<n2; ++j) 
     R[j] = arr[m + 1+ j]; 


    /* Merge the temp arrays */ 

    // Initial indexes of first and second subarrays 
    int i = 0, j = 0; 

    // Initial index of merged subarry array 
    int k = l; 
    while (i < n1 && j < n2) 
    { 
     if (L[i] < R[j]) 
     { 
      arr[k] = L[i]; 
      i++; 
     } 
     else if(L[i] > R[j]) 
     { 
      arr[k] = R[j]; 
      j++; 
     } 
     else{ 
      return false; 
     } 
     k++; 
    } 

    while (i < n1) 
    { 
     arr[k] = L[i]; 
     i++; 
     k++; 
    } 

    /* Copy remaining elements of L[] if any */ 
    while (j < n2) 
    { 
     arr[k] = R[j]; 
     j++; 
     k++; 
    } 

    return true; 
} 

// Main function that sorts arr[l..r] using 
// merge() 
boolean sort(char arr[], int l, int r) 
{ 
    if (l < r) 
    { 
     // Find the middle point 
     int m = (l+r)/2; 

     // Sort first and second halves 
     boolean left= sort(arr, l, m); 
     boolean right = sort(arr , m+1, r); 

     // Merge the sorted halves 
    return left&&right&&merge(arr, l, m, r); 
    } 
    return true; 
}