0

本「Cracking the Coding Interview」とこのStack Overflow questionでは、文字列にすべての一意の文字が含まれているかどうかを判断する関数について説明しています。ビットシフトを使用する本の回答は質問リンクにあります (ページの一番上の回答を参照してください)。ここでは繰り返しません。

Javaの回答にはO(N)の複雑さがあり、O(N)が実際に何を意味するのか理解できません。私は実際に、今書いたこの実装の時間計算量を知りたいと思っています。O(N) ですか？複雑さをどのように把握しますか？

static void Main(string[] args)
    {
        string stringToCheck ;
        bool hasAllUniqueChars = false;
        stringToCheck = "Test";

        hasAllUniqueChars = CheckForUniqueChars(stringToCheck);

        Console.WriteLine("String is Unique {0}", hasAllUniqueChars);
        Console.Read();
    }

    private static bool CheckForUniqueChars(string stringToCheck)
    {
        for (int i = 0; i < stringToCheck.Length - 1; i++)
        {
            for (int j = i; j < stringToCheck.Length - 1; j++)
            {
                if (Char.ToUpper(stringToCheck.ElementAt(i)) == 
                    Char.ToUpper(stringToCheck.ElementAt(j+1)))
                {
                    return false;
                }
            }
        }
        return true;           

    }

これは、Test、test、Hello に対して false を返し、SuperMan、SpiderMan、および Sponge に対して true を返し、正常に動作します。

ありがとうございました

4

4 に答える 4

6

あなたのアルゴリズムはO(n^2)、またはより正確には O( n ^2) である可能性があります。現在はO(n^3)であるため、可能性があります。

ElementAt()method はO(n) onIEnumerableであるため、ネストされた 2 つのループ内で実行されるため、メソッド全体はO(n^3)です。

s をbefore ループに変換し、拡張メソッドの代わりに配列インデクサーを使用することで、 O(n^2)を実行できます。stringchar[]ElementAt

private static bool CheckForUniqueChars(string stringToCheck)
{
    var chars = stringToCheck.ToCharArray();
    for (int i = 0; i < stringToCheck.Length - 1; i++)
    {
        for (int j = i; j < stringToCheck.Length - 1; j++)
        {
            if (Char.ToUpper(chars[i]) == Char.ToUpper(chars[j+1]))
            {
                return false;
            }
        }
    }
    return true;           
}

ボーナス: 別のO(n)アプローチ (HashSet<T>ルックアップはO(1)であるため):

private static bool CheckForUniqueChars(string stringToCheck)
{
    var characters = new HashSet<char>();

    foreach (var character in stringToCheck)
        if (!characters.Add(character))
            return false;

    return true;
}
于 2013-08-20T18:32:00.050 に答える
1

O(?) への回答ではありません

しかし、これは HashSet が O(1) に近いはずなので、O(N) に近いです。
注 HashSet.Count は O(1) です。 

HashSet<char> chars = new HashSet<char>();
string password = "password";
Int32 count = 0;
char cUpper;
foreach (char c in password)
{
    count++;
    cUpper = char.ToUpper(c);
    if (!chars.Add(char.ToUpper(c))) 
    {
        System.Diagnostics.Debug.WriteLine("not uniue");
        break;
    }
}
if(count == chars.Count) System.Diagnostics.Debug.WriteLine("uniue");

+1 Marcin がこの回答から ToUpper
を差し引いたものであることがわかり
ませんでした。

于 2013-08-20T18:49:51.847 に答える
0

編集：他のユーザーの提案によると、それはO（n ^ 3）、または3次多項式への成長に比例します。これは、ElementAt()が文字列をループするためです。

この複雑さの鍵は反復にあります。この構造:

for (each item in this thing)
{
   for(each item in this thing)
   {
      if (iterate through this thing to check a condition)
   }
}

三次多項式に比例する成長の次数を持つことになります。このような他のルーチンほど悪くはありません。これは、内側のループを介した内側の反復がインクリメントするにつれて小さくなるためです。ただし、文字列のすべての要素に対して反復し、それらの反復ごとに文字列全体を反復しています。アルゴリズムが O(n^3) の場合は、リファクタリングすることができます。

ElementAt ()呼び出しはありません。興味があれば、反復方法はSelection Sortと非常によく似ています。

于 2013-08-20T18:17:19.690 に答える