我们如何在常量复杂度或O（1）中交换2个数组？ [英] How can we swap 2 arrays in constant complexity or O(1)?

问题描述

我们如何在常量复杂度或O（1）中交换2个数组？
有一种方法，我们可以这样做吗？
i已尝试使用指针，但它给出错误

加上这个无法帮助，因为它只是互换指针，而不是数组

  #include< algorithm> 
 int AA [100]，* A = AA，BB [100]，* B = BB; 
 swap（A，B）; 
 

我已经尝试使用向量赋值运算符，但他们有LINEAR复杂性，即O（N）不常数所以有什么办法我们可以交换两个数组在O（1）？ （通过使用指针或其他）

我hv尝试在网上找到一个代码的链接（ http://codeforces.com/blog/entry/11971 ），但这不起作用。

解决方案

对于向量（ std :: vector std :: swap 从C ++标准

void swap（） vector& x）;

10效果：将*的内容和容量（）与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 :: vector中也做了相同的操作。

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.

解决方案

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.

这篇关于我们如何在常量复杂度或O（1）中交换2个数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！