确定Set S中是否存在两个元素,其和是x正确的解？

Question

摘自算法简介

描述一个Θ(n lg n)时间算法,给定一组n个整数和另一个整数x,确定S中是否存在两个元素,其和是x.

到目前为止,这是我用Java实现的最佳解决方案:

    public static boolean test(int[] a, int val) {
    mergeSort(a);

    for (int i = 0; i < a.length - 1; ++i) {
        int diff = (val >= a[i]) ? val - a[i] : a[i] - val;

        if (Arrays.binarySearch(a, i, a.length, diff) >= 0) {
            return true;
        }
    }

    return false;
}

现在我的第一个问题是:这是一个正确的解决方案吗？根据我的理解,mergeSort应该在O(n lg n)中执行排序,循环应该取O(n lg n)(n用于迭代乘以O(lg n)进行二进制搜索,得到O(2 l lg) n),所以它应该是正确的.

我的第二个问题是:有更好的解决方案吗？排序阵列必不可少？

Answer 1

您的解决方案似乎很好 是的,你需要排序,因为它是二进制搜索的先决条件.您可以对逻辑稍作修改,如下所示:

public static boolean test(int[] a, int val) 
{
    Arrays.sort(a);

    int i = 0;            // index of first element.
    int j = a.length - 1; // index of last element. 

    while(i<j)
    {
        // check if the sum of elements at index i and j equals val, if yes we are done.
        if(a[i]+a[j] == val)
            return true;
        // else if sum if more than val, decrease the sum.
        else if(a[i]+a[j] > val)
            j--;
        // else if sum is less than val, increase the sum.
        else
            i++;
    }
    // failed to find any such pair..return false. 
    return false;
}

Answer 2

还有另一个非常快速的解决方案:想象一下,你必须在Java中解决这个大约10亿个整数的问题.你知道,在Java中的整数从去-2**31+1到+2**31.

创建一个2**32十亿位的数组(500 MB,在今天的硬件上做的很简单).

迭代你的集合:如果你有一个整数,将相应的位设置为1.

到目前为止O(n).

在您的集合上再次迭代:对于每个值,检查您是否在"当前val - x"处设置了位.

如果你有一个,你就会返回true.

当然,它需要500 MB的内存.

但是,如果您有10亿个整数来解决这个问题,那么这应该围绕任何其他O(n log n)解决方案运行.

上).

Answer 3

1. 这是对的; 你的算法将在O(n lg n)时间内运行.

2. 有一个更好的解决方案:您计算diff的逻辑是不正确的.无论a[i]是大于还是小于val,你仍然需要差异val - a[i].

Answer 4

这是使用哈希集的O(n)解决方案:

  public static boolean test(int[] a, int val) {
      Set<Integer> set = new HashSet<Integer>();

      // Look for val/2 in the array
      int c = 0;
      for(int n : a) {
        if(n*2 == val)
          ++c
      }
      if(c >= 2)
         return true; // Yes! - Found more than one

      // Now look pairs not including val/2
      set.addAll(Arrays.asList(a));
      for (int n : a) {
         if(n*2 == val)
            continue;
         if(set.contains(val - n))
            return true;
      }

      return false;
   }