0

2 つの配列で同じ要素を見つけようとしていますが、要素間の最大距離は k に等しくなければなりません。

私の2つの配列（サイズが異なり、ソートされていない）AとB、k最大距離。

これは私がやったことですが、どこにエラーがあるのか​​ わかりません...

for (int i = 0; i<A.length; i++){
    for(int j = i; j < k || j < B.length; j++)
        if(A[i] == B[j]){
            //Print on console
            System.out.println(B[i]);
            j = k;
        }
    }
}

例えば：

A[3,7,5,9,10,15,16,1,6,2] 
B[4,8,5,13,1,17,2,11] 
k=6

出力は のはずですが5 1 2、理由はわかりません。私のプログラムでは しか表示されません5。誰かが理由を理解するのを手伝ってくれますか?

4

7 に答える 7

1 
for (int i = 0; i < A.length; i++) {
    int startIndex = Math.max(i - k + 1, 0);
    int endIndex = Math.min(i + k, B.length);
    for (int j = startIndex; j < endIndex; j++){
        if (A[i] == B[j]) {
            System.out.println(B[j]);
        }
    }
}

ええと、現在の要素を含めたり、除外したりして、距離を正確に求める方法がわかりません。また、(同じ範囲内の) 重複は、処理する特別なケースである可能性があります。

于 2013-08-19T11:44:22.793 に答える
0

何をすべきかわかりませんkが、あなたのアプローチはO(n^2)、これは多すぎます。

セットを使用すると、交点を非常に簡単に見つけることができます。

Set<Integer> aSet = new HashSet<Integer>();
// Adding an element to a set is O(1), this addAll operation is therefore O(n)
Collections.addAll(aSet, A);

// This loop is also O(n), as contains is O(1)
for (int b : B) {
    if (aSet.contains(b)) {
        // this b int is in A and b
    }
}

全体として、このアプローチはO(n)

編集

に関してはk、あなたがしていることについての私の理解はj < k、それをテストしているだけであり、5つしか出てこない理由を説明しています。によってテストされる i と j の間の距離をテストする必要があります

Math.abs(j-i) < k
于 2013-08-19T12:03:49.497 に答える
0

これが解決策です。確認しました、動作します。

あなたのエラー

  • 2 番目のループの初期化と停止条件が間違っています。i - k から開始し (0 未満の場合は 0 から開始)、j が i + k を超えると停止します。2 番目のループは、配列境界内の i - k と i + k の間で実行する必要があります。
  • 2 番目のループ変数を無条件に k に設定すると、予期しない動作が発生します。ループは古い値に戻る可能性があり、無限ループになります。
  • B[j] 値を制御しますが、B[i] 値を出力します。これにより、配列が範囲外の例外が発生する可能性があります。

int[] a = { 3, 7, 5, 9, 10, 15, 16, 1, 6, 2}; int[] b = { 4, 8, 5, 13, 1, 17, 2, 11 }; int k = 6;

    for (int i = 0; i < a.length; i++) {
        for (int j = ((i - k) < 0 ? 0 : i - k); j < i + k && j < b.length; j++) {

        if (a[i] == b[j]) {
            System.out.println(b[j]);
        }
    }  

    }
于 2013-08-19T11:35:23.960 に答える
0

これを試して：

for (int i = 0; i<A.length; i++){
            for(int j = 0; j < B.length; j++)
                if(A[i] == B[j] && Math.abs(j-i)<k){
                    //Print on console
                    System.out.println(B[j]);
                }
            }
于 2013-08-19T11:28:46.563 に答える
0

i から j を開始しているので、A の i 要素の後にある B の項目のみを反復します。

これはうまくいくかもしれません

    for (int i = 0; i<A.length; i++){
        for(int j =Math.max(0, i-k) ; j < Math.min(B.length, i+k); j++){
            if(A[i] == B[j]){
                System.out.println(B[j]);
            }
        }
    }

または：

    for (int i = 0; i<A.length; i++){
        for(int j = 0; j < B.lenght; j++){
            if(A[i] == B[j] && Math.abs(i-j)<=k){
                System.out.println(B[j]);
            }
        }
    }
于 2013-08-19T11:25:13.843 に答える