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

一个快速的测试是对数组中的数字求和，然后对下标求和。如果两者不相等，则可能存在重复。

对于更强的语句，对数组进行排序。这些值应与下标对齐。

Answer 3

一种解决方案是（伪代码）

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.