确定 Set S 中是否存在两个元素的总和恰好为 x - 正确解? [英] Determine whether or not there exist two elements in Set S whose sum is exactly x - correct solution?

问题描述

摘自算法导论

描述一个 Θ(n lg n) 时间算法给定一个由 n 个整数组成的集合 S 和另一个整数x，确定是否S中是否存在两个元素其总和正好是 x.

Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

这是我迄今为止用 Java 实现的最佳解决方案:

This is my best solution implemented in Java so far:

    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 lgn)，所以它应该是正确的.

Now my 1st question is: Is this a correct solution? From my understanding, mergeSort should perform the sort in O(n lg n), the loop should take O(n lg n) (n for the iteration multiplied by O(lg n) for the binary search, resulting in O(2n lg n), so it should be correct.

我的第二个问题是:有没有更好的解决方案?对数组进行排序是否必不可少?

My 2nd question is: Are there any better solutions? Is sorting the array essential?

推荐答案

您的解决方案看起来不错.是的，您需要排序，因为它是二分搜索的先决条件.您可以对您的逻辑稍作修改，如下所示:

Your solution seems fine. Yes you need to sort because its a pre requisite for binary search. You can make a slight modification to your logic as follows:

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

这篇关于确定 Set S 中是否存在两个元素的总和恰好为 x - 正确解?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！