2

私は、次の質問を提起するアルゴリズムの問​​題セットに取り組んでいます。

「文字列にすべての一意の文字が含まれているかどうかを判断します。配列のみを使用できると仮定します」.

私は実用的な解決策を持っていますが、時間の複雑さに関してより最適化されたものがあるかどうかを確認したいと思います。LINQ を使用したくありません。あなたが提供できる助けに感謝します！

static void Main(string[] args)
{
    FindDupes("crocodile");
}

static string FindDupes(string text)
{
    if (text.Length == 0 || text.Length > 256)
    {
        Console.WriteLine("String is either empty or too long");
    }

    char[] str = new char[text.Length];
    char[] output = new char[text.Length];

    int strLength = 0;
    int outputLength = 0;

    foreach (char value in text)
    {
        bool dupe = false;
        for (int i = 0; i < strLength; i++)
        {
            if (value == str[i])
            {
                dupe = true;
                break;
            }
        }
        if (!dupe)
        {
            str[strLength] = value;
            strLength++;

            output[outputLength] = value;
            outputLength++;
        }
    }
    return new string(output, 0, outputLength);
}
4

7 に答える 7

10

時間の複雑さだけが気になる場合は、文字を int 値にマップして、特定の文字値を以前に見たことがあるかどうかを記憶する bool 値の配列を用意します。

のようなもの... [テストされていません]

bool[] array = new bool[256]; // or larger for Unicode

foreach (char value in text)
  if (array[(int)value])
    return false;
  else
    array[(int)value] = true;

return true;
于 2012-10-01T04:29:08.050 に答える
3

これを試して、

    string RemoveDuplicateChars(string key)
    {
        string table = string.Empty;
        string result = string.Empty;
        foreach (char value in key)
        {
            if (table.IndexOf(value) == -1)
            {
                table += value;
                result += value;
            }
        }
        return result;
    }

利用方法

Console.WriteLine(RemoveDuplicateChars("hello"));
Console.WriteLine(RemoveDuplicateChars("helo"));
Console.WriteLine(RemoveDuplicateChars("Crocodile"));

出力

helo
helo
Crocdile
于 2012-10-01T04:10:33.123 に答える
1 
public boolean ifUnique(String toCheck){
    String str="";
    for(int i=0;i<toCheck.length();i++)
    {
         if(str.contains(""+toCheck.charAt(i)))
             return false;
         str+=toCheck.charAt(i);
    }
    return true;
}

編集：

toCheck が空の文字列である境界ケースを省略することも検討できます。

于 2012-10-01T05:04:58.677 に答える
0

次のコードが機能します。

 static void Main(string[] args)
    {
        isUniqueChart("text");
        Console.ReadKey();

    }

    static Boolean isUniqueChart(string text)
    {
        if (text.Length == 0 || text.Length > 256)
        {
            Console.WriteLine(" The text is empty or too larg");
            return false;
        }
        Boolean[] char_set = new Boolean[256];
        for (int i = 0; i < text.Length; i++)
        {
            int val = text[i];//already found this char in the string
            if (char_set[val])
            {
                Console.WriteLine(" The text is not unique");
                return false;
            }
            char_set[val] = true;
        }
        Console.WriteLine(" The text is unique");
        return true;
    }
于 2013-04-09T20:01:30.690 に答える