如何判断一个数组是否是 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;
}