c++ - 配列に重複した値がないことの検証

Question

サイズが n で、値の範囲が 0 から n-1 の配列があるとします。別の配列を使用せずに、値の重複がないことを検証する関数が必要です。

プロトタイプ: bool UniqueValues(unsigned arr[], size_t n);

これは就職面接のアルゴリズムに関する質問です。組み込みの std 関数の使用を提案しないでください。

Answer 1

配列をトラバースし、各要素について、arr[i] のインデックスで arr[i] を arr と交換します (たとえば、arr[1]=2 の場合、arr[2] と交換するので、arr[2]=2)。 . 値が重複しているかどうかは、arr[ arr[i] ] == arr[i] です。（arr [2]にすでに2があるときに、どこかに2が見つかりました）。

bool UniqueValues(unsigned arr[], size_t n)
{
    int val;
    for(size_t i=0;i<n;i++)
    {
        val = arr[i];
        if(val == arr[val] )  { if( val != i) return false; }  //  If the element is duplicated
        else {
            swap( arr[i], arr[val] );  //  Move the element to the index matching its value
            val = arr[i];
            if(val == arr[val] )  return false;  //  Another check for the swapped element
        }
    }
    return true;
}

Answer 2

簡単なテストは、配列内の数値を合計してから、添字を合計することです。2 つが等しくない場合は、重複している可能性があります。

より強力なステートメントについては、配列をソートします。値は添字と一致する必要があります。

Answer 3

1つの解決策は（疑似コード）

loop from i = 0 while i is smaller than length of array {
  loop from j = i + 1 while j is smaller than length of array {
    if array at index i equals array at index j {
      duplicate found. terminate the algorithm
    }
  }
}

no duplicate found.