java数组逻辑错误

Question

我编写了以下代码来解决一个问题，但它不起作用。这个问题的链接是here

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

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

Answer 2

如果复杂性应为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;
}

Answer 3

其思想是在外部循环，内部在外部循环 如果在路上看到它违反了规则，立即返回false 如果在最后，覆盖所有数组的内循环的索引返回true，否则返回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;
}

Answer 4

你必须做一个O（n）解，你的是O（n²）。你只需要三行字（好吧，有点作弊）：

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