如何确定数组是否为O（log N）中1-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）。

constexpr int N = 1000;
std::array<int, N> arr = {};      // zero-init
std::array<int, N + 1> hist = {}; // zero-init, we ignore element 0 and use elements 1..N
int counter = 0;

// writes  arr[i] = newv  in O(1)
void write(int i, int newv) {
    if(i < 0 || i > N-1)          // invalid index
        return;

    const int oldv = arr[i];      // read previous array entry

    if(oldv > 0 && oldv <= N) {   // decrease histogram
        if(hist[oldv] == 1)
            --counter;
        --hist[oldv];
        if(hist[oldv] == 1)
            ++counter;
    }

    arr[i] = newv;                // set array

    if(newv > 0 && newv <= N) {   // increase histogram
        if(hist[newv] == 1)
            --counter;
        ++hist[newv];
        if(hist[newv] == 1)
            ++counter;
    }
}

// tests for permutation in O(1)
bool testPermutation() {
    return counter == N;
}

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;
}