检查数组是否为排列的函数

Question

我必须写一个函数，它接受一个int数组参数，并检查它是否是一个排列。

我试过了:

bool permutationChecker(int arr[], int n){
for (int i = 0; i < n; i++){
//Check if the array is the size of n
if (i == n){
return true;
}
if (i == arr[n]){
return true;
}
}
return false;
}

但是输出说一些数组是排列，即使它们不是。

Answer 1

当您写入i == arr[n]时，不会检查i是否在数组中;检查位置n的元素是否为i。现在，情况更糟了，因为数组的大小是n，所以在位置n上没有有效的元素:它是UB，数组被过度索引了。

如果你想检查i是否在数组中，你需要扫描数组的每个元素。您可以使用std::find()来做到这一点。或者您可以对数组进行排序，然后检查i是否位于位置i:

bool isPermutation(int arr[], int n){
int* arr2 = new int[n]; // consider using std::array<> / std::vector<> if allowed
std::copy(arr, arr + n, arr2);
std::sort(arr2, arr2 + n);
for (int i = 0; i < n; i++){
if (i != arr2[i]){
delete[] arr2;
return false;
}
}
delete[] arr2;
return true;
}

Answer 2

检查输入是否包含每个值中的一个的一种方法是创建一个标志数组(作用类似于集合)，对于输入中的每个值，将相应索引的标志设置为true。如果这个标志已经设置，那么它就不是唯一的。如果这个值超出了范围，那么你马上就知道这不是一个排列。

现在，您通常希望为这个临时集分配额外的数据。但是，由于您的函数接受作为非常量数据的输入，我们可以使用一个技巧，即使用相同的数组，但通过使值为负来存储额外的信息。

它甚至适用于所有正的int值，因为从c++ 20开始，标准现在保证2的补码表示。这意味着对于每一个正整数，都存在一个负整数(反之则不存在)。

bool isPermutation(int arr[], int n)
{
// Ensure everything is within the valid range.
for (int i = 0; i < n; i++)
{
if (arr[i] < 1 || arr[i] > n) return false;
}
// Check for uniqueness. For each value, use it to index back into the array and then
// negate the value stored there. If already negative, the value is not unique.
int count = 0;
while (count < n)
{
int index = std::abs(arr[count]) - 1;
if (arr[index] < 0)
{
break;
}
arr[index] = -arr[index];
count++;
}
// Undo any negations done by the step above
for (int i = 0; i < count; i++)
{
int index = std::abs(arr[i]) - 1;
arr[index] = std::abs(arr[index]);
}
return count == n;
}

让我明确一点，使用复杂的魔法通常不是您应该选择的解决方案，因为它不可避免地难以理解和维护这样的代码。只要看看上面的代码，这应该是显而易见的。但是，假设你想避免任何额外的内存分配，你的数据类型是带符号的，并且你想在线性时间内完成操作……好吧，那这可能有用。

Answer 3

id=[0，…]的排列p，n-1]插入到id。因此，p中的任何值都不能重复，也不能为>=n。为了检查排列，您必须以某种方式验证这些属性。一种选择是对p进行排序，并比较它是否与id相等。另一种方法是计算设置的单个值的数量。

如果你检查(i == arr[i])而不是(i == arr[n])，你的方法几乎可以工作，但是你需要事先对数组进行排序，否则只有id会通过你的检查。此外，检查(i == arr[n])表现出未定义的行为，因为它访问了数组结束后的一个元素。最后，检查(i == n)没有做任何事情，因为i从0到n-1，所以它永远不会是== n。

有了这些信息，你可以修复你的代码，但要注意，这种方法会破坏原始输入。

---

如果你被迫使用数组，也许你的数组有固定的大小。例如:int arr[3] = {0,1,2};如果是这种情况，您可以使用在编译时已知大小的事实，并使用std::bitset。[如果不使用您的方法或这里给出的其他方法之一]

template <std::size_t N>
bool isPermutation(int const (&arr)[N]) {
std::bitset<N> bits;
for (int a: arr) {
if (static_cast<std::size_t>(a) < N)
bits.set(a);
}
return bits.all();
}

(现场演示)不需要传递大小，因为c++可以在编译时推断出来。这个解决方案也不分配额外的动态内存，但对于大型数组(sat>因为std::bitset存在于自动内存中，因此在堆栈上。