找到你要的答案

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

Q:创建一个函数,检查数组是否有两个相反的元素,或者小于2。(C++)

Create a function that checks whether an array has two opposite elements or not for less than n^2 complexity. Let's work with numbers.

Obviously the easiest way would be:

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;
}

I would like to ask if any of you guys can think of an algorithm that has a complexity less than n^2. My first idea was the following: 1) sort array ( algorithm with worst case complexity: n.log(n) ) 2) create two new arrays, filled with negative and positive numbers from the original array ( so far we've got -> n.log(n) + n + n = n.log(n)) 3) ... compare somehow the two new arrays to determine if they have opposite numbers

I'm not pretty sure my ideas are correct, but I'm opened to suggestions.

创建一个函数,检查数组是否有两个相反的元素,或者小于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;
}

I would like to ask if any of you guys can think of an algorithm that has a complexity less than n^2. My first idea was the following: 1) sort array ( algorithm with worst case complexity: n.log(n) ) 2) create two new arrays, filled with negative and positive numbers from the original array ( so far we've got -> n.log(n) + n + n = n.log(n)) 3) ... compare somehow the two new arrays to determine if they have opposite numbers

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

answer1: 回答1:

An important alternative solution is as follows. Sort the array. Create two pointers, one initially pointing to the front (smallest), one initially pointing to the back (largest). If the sum of the two pointed-to elements is zero, you're done. If it is larger than zero, then decrement the back pointer. If it is smaller than zero, then increment the front pointer. Continue until the two pointers meet.

This solution is often the one people are looking for; often they'll explicitly rule out hash tables and trees by saying you only have O(1) extra space.

一个重要的替代方案如下。数组排序。创建两个指针,一个指针指向前面(最小的),一个指向后面(最大)。如果两个指向元素的总和为零,那么你就完成了。如果大于零,则递减后指针。如果小于零,则增加前指针。继续直到两个指针相遇。

这个解决方案通常是一个人要找的,通常他们会明确地排除哈希表和树说你只有O(1)额外的空间。

answer2: 回答2:

I would use an std::unordered_set and check to see if the opposite of the number already exist in the set. if not insert it into the set and check the next element.

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);
}

Output:

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

Live Example

我会用一个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

活生生的例子

answer3: 回答3:

Let's see that you can simply add all of elements to the unordered_set and when you are adding x check if you are in this set -x. The complexity of this solution is O(n). (as @Hurkyl said, thanks)

UPDATE: Second idea is: Sort the elements and then for all of the elements check (using binary search algorithm) if the opposite element exists.

让我们看看,你可以简单地添加各种元素的unordered_set当你加入X检查,如果你在这集X的这个解决方案的复杂度为O(n)。(@ Hurkyl说,谢谢)

更新:第二个想法是:排序的元素,然后对所有的元素检查(使用二进制搜索算法),如果存在相反的元素。

answer4: 回答4:

You can do this in O(n log n) with a Red Black tree.

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

In C++, you wouldn't implement a Red Black tree for this purpose however. You'd use std::set, because it guarantees O(log n) search and insertion.

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

As Hurkyl mentioned, you could do better by just using std::unordered_set, which is a hashtable. This gives you O(1) search and insertion in the average case, but O(n) for both operations in the worst case. The total complexity of the solution in the average case would be O(n).

你可以在O(n日志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::设置,因为它保证O(log n)的搜索和插入。

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

作为hurkyl提到,你可以通过使用标准的做得更好::unordered_set,这是一个哈希表。这给你O(1)的搜索和插入的平均情况下,但O(N)的两个操作在最坏的情况下。在平均情况下的解决方案的总复杂度为O(n)。

c++  arrays  algorithm  complexity-theory