-2

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

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

4 回答 4

4

问题出在 else 部分。因为如果只有一次比较失败，您不能断定该元素不在内部数组中：

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;
}
于 2012-05-05T11:30:36.570 回答
1

如果复杂度应该是 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;
}
于 2012-05-05T11:39:55.233 回答
0

您必须制定一个 O(n) 解决方案，您的解决方案是 O(n 2 )。你只需要三行（好吧，有点作弊）：

int j = 0;
for (int in : inner) while (outer[j] != in) if (++j == outer.length) return false;
return true;
于 2012-05-05T11:37:11.710 回答
0

这个想法是在外部循环并在外部循环内部，如果在你看到它违反规则的方式上，如果最后循环遍历所有数组的内部索引返回 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;
}
于 2012-05-05T12:01:43.003 回答