배열 논리 오류

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

문제는 다른 부분에 있습니다. 당신이 내부 배열에하지에 그 요소를 결론 지을 수 없기 때문에 은 하나의 비교는 실패 경우 :

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

당신은해야합니다 :

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

당신이 할 수있는이 문제를 해결하려면 O (n) 솔루션을 사용하는 경우 O (n)입니다. 당신은 단지 세 줄 필요 (OK, 약간 부정 행위) :

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

Answer 3

을 복잡도가 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 4

아이디어는 루프에있는 외부 이상 및 바깥 쪽 내부의 내부 루프를 반복합니다. 규칙을 위반하면 규칙이 즉시 false를 반환합니다. 끝 부분에서 모든 배열에 대해 반복되는 내부 인덱스가 true이면 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; 
}