c++ - 如何确定数组是否是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;
}