我們如何交換2個恆定複雜度的數組或O（1）？

Question

我們如何交換2個恆定複雜度的數組或O（1）？ 有沒有辦法可以做到這一點？ 我已經使用指針嘗試，但它給錯誤

加上這不會幫助，因爲它僅僅是交換我一直在使用矢量賦值運算符，以及試圖指針而不是數組

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

，但他們有LINEAR複雜性，即O（N）不是常數，所以有什麼辦法可以在O（1）中交換兩個數組？ （通過使用指針或其他東西）

我試圖在網上搜索發現代碼鏈接（http://codeforces.com/blog/entry/11971），但這並沒有幫助。

Answer 1

使用std::swap（使用成員函數交換）向量（std::vector）的複雜度爲O（1）。

從C++標準

空隙交換（矢量& X）;

10影響：將* this的內容和容量（）與x的內容和容量（）交換。

11複雜度：恆定時間。

如果使用operator 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 ::向量來完成。