0

問題

繰り返し数の配列で繰り返しのない数のリストを見つけます。

私の解決策

   public static int[] FindNonRepeatedNumber(int[] input)
    {
        List<int> nonRepeated = new List<int>();
        bool repeated = false;

        for (int i = 0; i < input.Length; i++)
        {
            repeated = false;

            for (int j = 0; j < input.Length; j++)
            {
                if ((input[i] == input[j]) && (i != j))
                {
                    //this means the element is repeated.
                    repeated = true;
                    break;
                }
            }

            if (!repeated)
            {
                nonRepeated.Add(input[i]);
            }
        }

        return nonRepeated.ToArray();
    }

時間と空間の複雑さ 時間の複雑さ = O(n^2) 空間の複雑さ = O(n)

上記の計算された時間の複雑さ、およびこのプログラムをより効率的かつ高速にするにはどうすればよいかわかりません。

4

3 に答える 3

2

あなたが提供したアルゴリズムの複雑さは ですO(n^2)。

ハッシュマップを使用してアルゴリズムを改善します。擬似コードは次のとおりです。

public static int[] FindNonRepeatedNumbers(int[] A)
{
Hashtable<int, int> testMap= new Hashtable<int, int>();

for (Entry<Integer, String> entry : testMap.entrySet()) {
            tmp=testMap.get(A[i]);
            testMap.put(A[i],tmp+1);
}

/* Elements that are not repeated are:

Set set = teatMap.entrySet(); 
// Get an iterator 
Iterator i = set.iterator(); 
// Display elements 
while(i.hasNext()) { 
Map.Entry me = (Map.Entry)i.next(); 
if(me.getValue() >1)
{
    System.out.println(me.getValue()); 
}
}

操作: ここで行ったことは、入力配列の要素であるハッシュマップへのキーを持つハッシュマップを使用したことです。ハッシュマップの値は、各要素のカウンターのようなものです。そのため、要素が 1 回発生すると、そのキーの値は 1 になり、その後、入力配列内の要素の繰り返しに基づいてキー値がインクリメントされます。

最後に、ハッシュマップをチェックして、繰り返されない要素であるハッシュ値 1 の要素を表示します。入力配列の長さが の場合、このアルゴリズムの計算量はO(k)ハッシュマップの作成とO(k)検索ですk。これは よりもはるかに高速ですO(n^2)。最悪のケースは、繰り返される要素がまったくない場合です。疑似コードは面倒かもしれませんが、このアプローチは私が考えることができる最良の方法です。

于 2012-06-18T18:16:18.437 に答える
0

時間計算量O（n）は、内部ループを持つことができないことを意味します。完全な内部ループはO（n ^ 2）です。

于 2012-06-18T17:29:59.937 に答える
0

2 つのポインター。始まりと終わり。同じ文字に達したときに開始をインクリメントし、開始位置と終了位置、参照用の長さを保存します...それ以外の場合は終了をインクリメントします..リストの最後までこれを続けます..すべての出力を比較すると、一意の番号の最長の連続リストが得られます。これが質問に必要なものであることを願っています。線形アルゴリズム。

void longestcontinuousunique(int arr[])
{
int start=0;
int end =0;
while (end! =arr.length())
{
if(arr[start] == arr[end])
{
start++;
savetolist(start,end,end-start);
}
else
end++
}

return maxelementof(savedlist);
    }
于 2012-06-18T17:51:10.073 に答える