c++ - 我们如何以恒定复杂度或 O(1) 交换 2 个数组？

Question

我们如何以恒定的复杂度或 O(1) 交换 2 个数组？我们有办法做到这一点吗？我试过使用指针，但它给出了一个错误

此外，这无济于事，因为它只是交换指针而不是数组:

#include <algorithm>
int AA[100], *A=AA, BB[100], *B=BB;
swap(A, B);

我也尝试过使用 vector 赋值运算符，但它们具有线性复杂性，即 O(N) 不是常量。那么，有什么方法可以在 O(1) 中交换两个数组？ (通过使用指针或其他东西)

我尝试在互联网上搜索并找到了指向 codeforces ( http://codeforces.com/blog/entry/11971 ) 的链接，但这没有帮助。

Answer 1

对 vector (std::vector) 使用 std::swap(使用成员函数 swap)的复杂度为 O(1).

来自 C++ 标准:

void swap(vector& x);

10 作用:将 *this 的内容和 capacity() 与 x 的内容和 capacity() 进行交换。

11 复杂性:常数时间。

如果使用运算符 new 动态分配数组，您可以用恒定时间“交换数组”。在这种情况下，您确实只能交换指向数组第一个元素的指针。

例如:

#include <iostream>
#include <algorithm>

int main() {
    int **a = new int *[2];
    a[0] = new int[5] { 0, 1, 2, 3, 4 };
    a[1] = new int[5] { 5, 6, 7, 8, 9 };
    
    for ( size_t i = 0; i < 2; i++ ) {
        for ( size_t j = 0; j < 5; j++ ) {
            std::cout << a[i][j] << ' ';
        }
        std::cout << std::endl;
    }
    
    std::cout << std::endl;
    
    std::swap( a[0], a[1] );    

    for ( size_t i = 0; i < 2; i++ ) {
        for ( size_t j = 0; j < 5; j++ ) {
            std::cout << a[i][j] << ' ';
        }
        std::cout << std::endl;
    }
    
    std::cout << std::endl;
    
    delete [] a[0];
    delete [] a[1];
    delete [] a;
    
    return 0;
}

输出是:

0 1 2 3 4 
5 6 7 8 9 

5 6 7 8 9 
0 1 2 3 4 

其实在std::vector中也做了同样的操作。