java - 配列論理エラー

Question

問題を解決するために次のコードを書きましたが、機能しません。質問へのリンクはこちらです。

  public boolean linearIn(int[] outer, int[] inner) {

    boolean result = false;

        if(inner.length == 0)
            return true;

        index: for(int x: inner) {
                    for(int y: outer) {
                        if(x==y) {
                            result = true;
                            break;
                        }
                        else {
                            result = false;
                            break index;
                        }
                    }
                }
        return result;
    }

score 4 · Accepted Answer

問題はのelse部分にあります。1 つの比較だけが失敗した場合、要素が内部配列にないと結論付けることはできないため、次のようになります。

if(x==y) {
 result = true;  // ele present.
 break;
} else { 
 result = false; // can't conclude ele is absent..you might find it later.
 break index;
}

これを修正するには、次のようにします。

public boolean linearIn(int[] outer, int[] inner) {

        for(int x: inner) {
                // assume x is absent.
                boolean result = false;
                for(int y: outer) {
                        // x found in outer.
                        if(x==y) {
                                // make result positive.
                                result = true;
                                // no need to look any further.
                                break;
                        }
                }
                // at this point not all elements of inner are 
                // tested for presence in outer. But one missing ele
                // would mean we return false.
                if(result == false) return false;
        }
        // all ele of inner are present in outer..return true.
        return true;
}

score 1 · Accepted Answer

複雑さが O(n) の場合、仮想コード:

public boolean linearIn (int[] outer, int[] inner) {

 int in=0;
    for(int i :outer){
        if(in==inner.length) return true;
        if(inner[in]==i)
            in++;}
    if(in==inner.length)return true;
    return false;
}

score 0 · Accepted Answer

アイデアは、外側をループし、途中でそのブレークが表示された場合、外側の内側をループすることです。最後にすべての配列をループした内側のインデックスが true を返す場合、ルールはすぐに false を返します。それ以外の場合は false を返します。

public boolean linearIn(int[] outer, int[] inner) {
    int i, j;
    // loop over the outer
    for(i = 0, j =0; i < outer.length && j < inner.length; i++) {
       // move to the last same value on the outer
       while(i < outer.length-1 && outer[i] == outer[i+1]) {
           i++;
       }
       // move to the last same value on the inner
       while(j < inner.length-1 && inner[j] == inner[j+1]) {
           j++;
       }
       // immediate false
       if(inner[j] < outer[i]) {
           return false;
       }
       // match - move to the next inner
       if(inner[j] == outer[i]) {
           j++;
       }
    }
    if(j == inner.length) {
        return true;
    }
    return false;
}

score 0 · Accepted Answer

O(n) ソリューションを作成する必要があります。あなたのソリューションは O(n ² ) です。必要なのはたったの 3 行です (わかりました、少しごまかしています)。

int j = 0;
for (int in : inner) while (outer[j] != in) if (++j == outer.length) return false;
return true;

java - 配列論理エラー

4 に答える 4

Related

Reference