确定集合 S 中是否存在两个元素，其总和正好是 x - 正确的解？

arrays algorithm java

2022-09-01 04:56:45

摘自《算法导论》

描述一个 Θ（n lg n）时间算法，该算法给定一组 n 个整数和另一个整数 x 的集合 S，确定 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（2n lg n），因此它应该是正确的。

我的第二个问题是：有没有更好的解决方案？对数组进行排序是否至关重要？

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

答案 2

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

创建一个具有十亿位（500 MB，在当今的硬件上做起来微不足道）的数组。2**32

循环访问您的集合：如果您有一个整数，请将相应的位设置为 1。

到目前为止，O（n）。

再次迭代您的集合：对于每个值，检查是否在“当前 val - x”处设置了位。

如果有，则返回 true。

当然，它需要500 MB的内存。

但是，如果您要用10亿整数来解决这个问题，那么这将绕过任何其他O（n log n）解决方案。

O（n）.