如何在恒定复杂度或O(1)
中交换2个数组?我们有办法做到这一点吗?我试过使用指针,但它给出了一个错误
此外,这也无济于事,因为它只是交换指针,而不是数组:
#include <algorithm>
int AA[100], *A=AA, BB[100], *B=BB;
swap(A, B);
我也尝试过使用向量赋值运算符,但它们具有线性复杂性,即O(N)
不是常数。那么,有什么方法可以在O(1)
中交换两个阵列吗?(通过使用指针或其他东西)
我试着在互联网上搜索,发现了一个代码部队的链接(http://codeforces.com/blog/entry/11971),但这于事无补。
对向量(std::vector
)使用std::swap
(使用成员函数交换)具有O(1)
的复杂性。
来自C++标准:
void swap(vector& x);
10效果:将*this的内容和容量()与x.的内容和能力交换
11复杂性:恒定时间。
你可以"交换阵列";如果它们是用运算符CCD_ 7动态分配的,则具有恒定的时间。在这种情况下,您实际上只能交换指向数组的第一个元素的指针。
例如:
#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
中也进行了相同的操作。