假设我们有一个大小为 n 的数组,其值范围从 0 到 n-1。需要一个验证没有重复值的函数,而不使用另一个数组。
原型: bool UniqueValues(unsigned arr[], size_t n);
这是一个求职面试的算法问题,请不要建议使用内置的std函数。
遍历数组,对于每个元素,将 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;
}
一个快速的测试是对数组中的数字求和,然后对下标求和。如果两者不相等,则可能存在重复。
对于更强的语句,对数组进行排序。这些值应与下标对齐。
一种解决方案是(伪代码)
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.