如何在 C 或 C++ 中以 O(1) 时间复杂度交换两个字符串？

Question

我想交换两个字符串而不复制所有字符，因为这需要更多时间。我认为使用字符串地址可以在 O(1) 时间复杂度内完成。但我无法弄清楚。你能帮我做吗？

我尝试使用地址。但是有一些语法错误。

#include <bits/stdc++.h>
using namespace std;

int main ()
{
  std::string buyer ("money");
  std::string seller ("goods");
  string *temp;
  
  std::cout << "Before the swap, buyer has " << buyer;
  std::cout << " and seller has " << seller << '\n';
  cout<< " Before the swap "<<(&buyer)<<" "<<(&seller)<<"\n";
  temp=(&buyer); (&buyer)=(&seller); (&seller)=temp;
  cout<< " After the address swap "<<(&buyer)<<" "<<(&seller)<<"\n";
  swap (buyer,seller);
  cout<< " After the built-in swap "<<(&buyer)<<" "<<(&seller)<<"\n";

  return 0;
}

Answer 1

正如评论者所指出的，

std::swap(buyer, seller)

在 O(1) 中做你想做的（通过交换两个字符串内的指针成员变量，not 通过复制字符串的字符），所以没有理由使用指针- 间接除了可能作为学习练习。

因此，仅作为学习示例，您可以通过以下方式仅使用指针来完成此操作：

#include <string>
#include <iostream>

int main ()
{
  std::string buyer ("money");
  std::string seller ("goods");

  std::string * temp1 = &buyer;
  std::string * temp2 = &seller;

  std::cout << "Before the swap, buyer has " << *temp1;
  std::cout << " and seller has " << *temp2 << '\n';

  // These three lines are equivalent to std::swap(temp1, temp2)
  std::string * temp3 = temp1;
  temp1 = temp2;
  temp2 = temp3;

  std::cout << "After the swap, buyer has " << *temp1;
  std::cout << " and seller has " << *temp2 << '\n';

  return 0;
}