具有用于“二和"的O(n ^ 2)算法，转换为O(n)线性解 [英] Have O(n^2) algorithm for "two-sum", convert to O(n) linear solution

问题描述

我对经典的两和问题有O(n ^ 2)解.其中A [1 ... n]对正整数排序. t是一些正整数.

I have an O(n^2) solution to the classic two-sum problem. Where A[1...n] sorted array of positive integers. t is some positive integer.

需要证明A包含两个不同的元素a和b. a + b = t

Need to show that A contains two distinct elements a and b s.t. a+ b = t

到目前为止，这是我的解决方案:

Here is my solution so far:

t = a number;
    for (i=0; i<A.length; i++)
          for each A[j]
            if A[i] + A[j] == t
                return true
    return false

如何使它成为线性解决方案? O(n)抓挠我的头，试图弄清楚.

How do I make this a linear solution? O(n) scratching my head trying to figure it out.

到目前为止，这是我想到的一种方法.我将从A的开头开始，j从A的末尾开始.我将递增，j将递减.因此，在for循环中，我将有两个计数器变量i& j.

Here's an approach I have in mind so far. i will start at the beginning of A, j will start at the end of A. i will increment, j will decrement. So I'll have two counter variables in the for loop, i & j.

推荐答案

有两种方法可以对此进行改进.

There are couple of ways to improve upon that.

1. 您可以扩展算法，但是可以对每个术语进行简单的搜索，而不是对每个术语进行简单的搜索

t = a number
for (i = 0; i < A.length; i++)
  j = binarySearch(A, t - A[i], i, A.length - 1)
  if (j != null) 
      return true
return false

二进制搜索是通过O(log N)个步骤完成的，因为您对数组中的每个元素都执行了二进制搜索，所以整个算法的复杂度将为O(N * log N) 这已经是对O(N ^ 2)的巨大改进，但是您可以做得更好.

Binary search is done by O(log N) steps, since you perform a binary search per every element in the array, the complexity of the whole algorithm would be O(N*log N) This already is a tremendous improvement upon O(N^2), but you can do better.

1. 让我们以总和11和数组1、3、4、8、9为例. 您已经可以看到(3,8)满足总和.为了发现这一点，假设有两个指针，一旦指向数组的开头(1)，我们将其命名为H并用 bold 表示，另一个指向数组的末尾( 9)，我们将其称为T并用强调表示.

1. Let's take the sum 11 and the array 1, 3, 4, 8, 9 for example. You can already see that (3,8) satisfy the sum. To find that, imagine having two pointers, once pointing at the beginning of the array (1), we'll call it H and denote it with bold and another one pointing at the end of the array (9), we'll call it T and denote it with emphasis.

1 3 4 8 9

现在两个指针的总和是1 + 9 = 10. 10小于所需的总和(11)，无法通过移动T指针达到所需的总和，因此我们将H指针向右移动:

Right now the sum of the two pointers is 1 + 9 = 10. 10 is less than the desired sum (11), there is no way to reach the desired sum by moving the T pointer, so we'll move the H pointer right:

1 3 4 8 9

3 + 9 = 12，它大于所需的总和，无法通过移动H指针来达到所需的总和，向右移动将进一步增加总和，向左移动将我们带到初始状态，所以我们将T指针向左移动:

3 + 9 = 12 which is greater than the desired sum, there is no way to reach the desired sum by moving the H pointer, moving it right will further increase the sum, moving it left bring us to the initital state, so we'll move the T pointer left:

1 3 4 8 9

3 + 8 = 11<-这是所需的总和，我们完成了.

3 + 8 = 11 <-- this is the desired sum, we're done.

因此，算法规则包括向左移动H指针或向右移动T指针，当两个指针的总和等于所需的总和或H和T相交(T变小时，我们就完成了)比H).

So the rules of the algorithm consist of moving the H pointer left or moving the T pointer right, we're finished when the sum of the two pointer is equal to the desired sum, or H and T crossed (T became less than H).

t = a number
H = 0
T = A.length - 1
S = -1

while H < T && S != t
    S = A[H] + A[T]
    if S < t
        H++
    else if S > t
        T--

return S == t

很容易看到该算法在O(N)运行，因为我们最多遍历每个元素一次.

It's easy to see that this algorithm runs at O(N) because we traverse each element at most once.

这篇关于具有用于“二和"的O(n ^ 2)算法，转换为O(n)线性解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！