如何告诉数组O（log N）中的排列？

Question

长度为n的序列如果一次包含从1到n的所有整数，则称为置换。

您能否确定数组是否为O（log N）中的排列？

Answer 1

您的意思是说，数组是否包含排列？O（log N）是不够的：您需要O（N）才能读取所有元素。O（N * log N）足以对数组进行排序，然后判断它是否是O（N）中的一个排列是微不足道的。

[您可以在每次写入阵列期间更新直方图，也可以更新计数器，即多少个直方图条目正好为1。这将使每次更新的成本为O（1），而实际测试的成本为O（1）。

Answer 2

如果不查看条目的每个条目，就无法判断数组是否为置换，因此算法中至少需要n个步骤。

一个简单的线性时间解决方案是尝试计算逆排列（假设基于0的索引）：

std::vector<int> inverse(n, -1);

for (int i = 0; i < n; ++i) {
    if (array[i] < 0 || array[i] >= n || inverse[array[i]] != -1) {
        break; // not a permutation!
    }
    inverse[array[i]] = i;
}