algorithm - 他の数字が 2 回以上出現する場合に、リスト内の 1 つの数字を検索する

Question

問題は、リスト内の単一の数字の検索から拡張されています

問題をこれに拡張すると: 他のすべての数字がちょうど k 回出現するリストで、1 回だけ出現する数字を見つけるための最良のアルゴリズムは何でしょうか?

誰もが良い答えを持っていますか？

たとえば、A = { 1, 2, 3, 4, 2, 3, 1, 2, 1, 3 }、この場合、k = 3. O(n) で単一の数値「4」を取得するにはどうすればよいですか時間と空間の複雑さは O(1) ですか?

Answer 1

配列内のすべての要素が n 未満で 0 より大きい場合。配列を a とし、各追加
について配列をトラバースします。 ここで、配列を再度トラバースします。より小さい位置とより大きい位置(1 ベースのインデックスを想定) が答えです。 a[i]na[(a[i])%(n)]
a[i]2*nn

少なくとも 1 つの要素が n より大きい場合、このメソッドは機能しません。その場合、Jayram が提案する方法を使用する必要があります

編集:
配列を取得するmod nには、配列内のすべての要素に適用するだけです

Answer 2

バナルンのソリューションによると（小さな修正あり）：

アルゴリズム条件:

 for each i arr[i]<N (size of array)
 for each i arr[i]>=0 (positive)

アルゴリズム:

int[] arr = { 1, 2, 3, 4, 2, 3, 1, 2, 1, 3 };
for (int i = 0; i < arr.Length; i++)
{
    arr[(arr[i])%(arr.Length)] += arr.Length;
    if(arr[i] < arr.Length)
        arr[i] = -1;
}
for (int i = 0; i < arr.Length; i++)
{

     if (arr[i] - 3 * arr.Length <0 && arr[i]!=-1)
          Console.WriteLine("single number = "+i);
}

このソリューションは、時間の複雑性が O(N) で、空間の複雑性が O(1) です。

注: このアルゴリズムも、すべての数値が正で、すべての数値が N より小さい場合にのみ機能します。