配列 - java list 検索 複数




セットSに2つの要素が存在するかどうかを判定します。その要素の和は正確にx正しい解ですか? (6)

  1. これは正しいです; アルゴリズムはO(ng n)時間で実行されます。

  2. より良い解決策があります:diffを計算するためのロジックが間違っています。 a[i]valより大きいか小さいかにかかわらず、あなたは依然としてval - a[i]必要があります。

アルゴリズム入門から取られた

n個の整数の集合Sともう1つの整数xが与えられたときに、その和が正確にxであるSに2つの要素が存在するかどうかを決定するΘ(n lg n)時間アルゴリズムを記述する。

これはこれまで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(ng n)のソートを実行する必要があります。ループはO(ng n)(nは繰り返し回数がO(lg n) n)、正しいはずです。

私の第二の質問は:より良い解決策はありますか? 配列の並べ替えは必須ですか?


あなたの分析は正しいです。はい、配列をソートする必要があります。そうしないと、バイナリ検索は機能しません。


あなたの解決策はうまくいくようです。 はい、バイナリ検索の前提条件であるため、ソートする必要があります。 次のようにロジックを少し変更することができます:

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

ここでは、いくつかの条件をmergesortに追加することで、代わりの解決法があります。

public static void divide(int array[], int start, int end, int sum) {

    if (array.length < 2 || (start >= end)) {
        return;
    }
    int mid = (start + end) >> 1; //[p+r/2]
    //divide
    if (start < end) {
        divide(array, start, mid, sum);
        divide(array, mid + 1, end, sum);
        checkSum(array, start, mid, end, sum);
    }
}

private static void checkSum(int[] array, int str, int mid, int end, int sum) {

    int lsize = mid - str + 1;
    int rsize = end - mid;
    int[] l = new int[lsize]; //init
    int[] r = new int[rsize]; //init

    //copy L
    for (int i = str; i <= mid; ++i) {
        l[i-str] = array[i];
    }
    //copy R
    for (int j = mid + 1; j <= end; ++j) {
        r[j - mid - 1] = array[j];
    }
    //SORT MERGE
    int i = 0, j = 0, k=str;
    while ((i < l.length) && (j < r.length) && (k <= end)) {
    //sum-x-in-Set modification
    if(sum == l[i] + r[j]){
        System.out.println("THE SUM CAN BE OBTAINED with the values" + l[i] + " " + r[j]);            
    }
     if (l[i] < r[j]) {
            array[k++] = l[i++];
        } else {
            array[k++] = r[j++];
        }
    }
    //left over
    while (i < l.length && k <= end) {
        array[k++] = l[i++];
          //sum-x-in-Set modification
        for(int x=i+1; x < l.length; ++x){
            if(sum == l[i] + l[x]){
                System.out.println("THE SUM CAN BE OBTAINED with the values" + l[i] + " " + l[x]);
            }
        }
    }
    while (j < r.length && k <= end) {
        array[k++] = r[j++];
          //sum-x-in-Set modification
        for(int x=j+1; x < r.length; ++x){
            if(sum == r[j] + r[x]){
                System.out.println("THE SUM CAN BE OBTAINED with the values" + r[j] + " " + r[x]);
            }
        }
    }
}

しかし、このアルゴリズムの複雑さは依然としてTHETA(nlogn)とは異なります。


簡単な解決策は、並べ替えの後、配列の両端からポインタを下に移動し、xに合計するペアを探します。 合計が大きすぎる場合は、右ポインタを減らします。 低すぎる場合は、左の値をインクリメントします。 ポインタが交差する場合、答えはノーです。


非常に速い解決策がもう1つあります。Javaでこの問題を約1億の整数で解決しなければならないと想像してください。 あなたはJavaの整数が-2**31+1から+2**31ことを知っています。

2**32億ビット(500 MB、今日のハードウェア上で行うことは自明)の配列を作成します。

あなたのセットを反復する:整数を持つ場合、対応するビットを1に設定する。

今まではO(n)であった。

あなたのセットをもう一度繰り返します:それぞれの値に対して、「現在のval-x」にビットが設定されているかどうかを確認します。

あなたが持っているなら、あなたは真実を返します。

500 MBのメモリが必要です。

しかし、これは10億の整数でこの問題を解決するためには、他のO(n log n)の解の周りを走ります。

に)。







algorithm