How can we swap 2 arrays in constant complexity or

问题:

How can we swap 2 arrays in constant complexity or O(1)? is there a way that we can do this? i have tried using pointers but it is giving error

plus this wont help because it is just interchanging the pointers but not the arrays

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

I have tried using vectors assignment operator as well but they have LINEAR complexity i.e O(N) not constant so is there any way we can swap two arrays in O(1)? (by using pointers or something else)

i hv tried searching on net found a link of codeforces ( http://codeforces.com/blog/entry/11971 ) but this is not helping.

回答1:

Using std::swap (that uses member function swap) for vectors (std::vector) has complexity of O(1).

From the C++ Standard

void swap(vector& x);

10 Effects: Exchanges the contents and capacity() of *this with that of x.

11 Complexity: Constant time.

You could "swap arrays" with a constant time if they were allocated dynamically with operator new. In this case you indeed could swap only pointers that point to the first elements of the arrays.

For example

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

The output is

0 1 2 3 4 
5 6 7 8 9 

5 6 7 8 9 
0 1 2 3 4 

In fact the same operation is done in std::vector.