创建一个函数，检查数组是否具有两个相反的元素，复杂度小于 n^2。 (C++)

Question

创建一个函数来检查一个数组是否有两个相反的元素，复杂度小于 n^2。让我们来处理数字吧。

显然最简单的方法是：

bool opposite(int* arr, int n) // n - array length
{
 for(int i = 0; i < n; ++i)
  { 
    for(int j = 0; j < n; ++j)
     {
       if(arr[i] == - arr[j])
          return true;
     }
  }

  return false;
}

请问各位有没有想出一个复杂度小于n^2的算法。我的第一个想法如下： 1）排序数组（最坏情况复杂度算法：n.log(n)） 2）创建两个新数组，填充原始数组中的负数和正数（到目前为止我们有 -> n.log(n) + n + n = n.log(n)） 3) ...以某种方式比较两个新数组以确定它们是否具有相反的数字

我不太确定我的想法是否正确，但我愿意接受建议。

Answer 1

让我们看看您可以简单地将所有元素添加到 unordered_set 中，当您添加 x 时检查您是否在这个集合 -x 中。该解决方案的复杂度为 O(n)。（正如@Hurkyl 所说，谢谢）

更新：第二个想法是：对元素进行排序，然后对所有元素检查（使用二进制搜索算法）是否存在相反的元素。

Answer 2

您可以使用红黑树在 O(n log n) 中完成此操作。

t := empty tree
for each e in A[1..n]
    if (-e) is in t:
        return true
    insert e into t
return false

但是，在 C++ 中，您不会为此目的实现红黑树。您会使用 std::set，因为它保证 O(log n) 搜索和插入。

std::set<int> s;
for (auto e : A) {
    if (s.count(-e) > 0) {
        return true;
    }
    s.insert(e);
}
return false;

正如 Hurkyl 提到的，您可以通过使用哈希表 std::unordered_set 来做得更好。这在平均情况下为您提供 O(1) 搜索和插入，但在最坏情况下为这两个操作提供 O(n)。在平均情况下，解决方案的总复杂度为 O(n)。

Answer 3

我会使用 std::unordered_set 并检查数字的相反数是否已存在于集合中。如果没有将其插入集合并检查下一个元素。

std::vector<int> foo = {-10,12,13,14,10,-20,5,6,7,20,30,1,2,3,4,9,-30};
std::unordered_set<int> res;
for (auto e : foo)
{
    if(res.count(-e) > 0)
        std::cout << -e << " already exist\n";
    else 
        res.insert(e);
}

输出：

opposite of 10 alrready exist
opposite of 20 alrready exist
opposite of -30 alrready exist

Live Example

Answer 4

一个重要的替代解决方案如下。对数组进行排序。创建两个指针，一个最初指向前面（最小），一个最初指向后面（最大）。如果两个指向的元素之和为零，则您完成了。如果它大于零，则递减后向指针。如果它小于零，则递增前指针。继续，直到两个指针相遇。

这个解决方案通常是人们正在寻找的；通常他们会明确排除哈希表和树，说你只有 O(1) 额外的 space.

创建一个函数，检查数组是否具有两个相反的元素，复杂度小于 n^2。 (C++)

Create a function that checks whether an array has two opposite elements or not for less than n^2 complexity. (C++)

c++

arrays

algorithm

complexity-theory