算法简介算法类型

Question

我正在学习算法，正在阅读“算法导论第三版”这本书，在一个问题部分，它描述了下一个问题：

描述一个O(n*-time(N))-time算法，该算法在给定一个由n个整数和另一个整数x组成的集合S的情况下，确定S中是否存在两个和恰好等于x的元素。

我不知道它是提出有序集还是无序集？

Answer 1

设x是你想要得到的和。首先对数组进行排序。然后，对于array (ai)中的每个元素，使用二进制搜索查找数组中是否存在(x-ai)。

伪代码：

 sort(a,n)
 for i : 1 to n
     if(binary_search(a,i+1,n-1,x-a[i]))
          return true
 return false

其他方法:排序后，先用两个指针，最后用两个指针检查：

 while(first < last) {
        if(a[first]+a[last] == x) return true;
        else if(a[first]+a[last] < x) first++;
       else if(a[first]+a[last] > x) last--;
    }
    return false;

Answer 2

给定一个已排序的数组，您可以找到是否存在一对具有O(n)算术运算的x求和。

i := 0
j := len(A) - 1
while i < j {
    if A[i] + A[j] < x {
        i += 1
    } else if A[i] + A[j] == x {
        return true
    } else if A[i] + A[j] > x {
        j -= 1
    }
}
return false

考虑到这一点，您可以通过对数组进行排序，然后使用上面的算法，使用O(n log n)算术运算来确定是否有任何数组包含一对求和为x的元素。