두 목록에서 누락 된 숫자 찾기

Question

질문 : 동일한 숫자가 포함 된 두 개의 알 수없는 정수 목록이 있다고 가정 해 보겠습니다. 그러나 목록 중 하나에 숫자가 누락되었습니다. 잃어버린 숫자를 찾는 가장 효과적인 방법은 무엇입니까?

내 접근 :이 같은 루프 중첩 적이 :

public int findMissing(int [] list1,int [] list2){ 
    for(int i =0; i < list1.length(); i++){ 
     for(int j=0; j < list2.length(); j++){ 
      if(list1[i] != list2[j] && j == list2.length()-1) 
      return list2[j]; 
    } 
} 
return; 

설명은 첫 번째 목록에있는 모든 항목과 두 번째 목록의 각 항목을 비교합니다. 루프가 끝나고 두 번째 목록의 번호가 첫 번째 목록에없는 경우 해당 번호를 반환하십시오.

더 좋은 방법이 있는지 알려주세요. 실행 시간 측면에서 더 좋습니다.

Answer 1

(list1의 모든 숫자 합계) - (list2의 모든 숫자 합계) = 찾고있는 숫자입니다.

첫 번째 목록에는 추가 숫자가 포함 된 것으로 가정하고, 그렇지 않으면 해당 번호의 음수 값을 반환합니다.

Answer 2

목록이 동일하다고 가정하면 목록을 정렬 할 수 있습니다. 그런 다음 루프를 중첩 할 필요가 없습니다. 같은 위치에서 두 목록을 모두 확인할 수 있으며, 두 목록이 동일해야합니다. 그렇지 않은 경우 목록 중 하나가 다릅니다 (올바른 것으로 간주되는 목록에 따라 다름). 런타임은 전체 목록을 확인하기 위해 해당 지점에서 선형입니다.

Answer 3

두 목록을 합하는 것 (오버플로가 발생할 수 있음)보다 나은 해결책은 목록을 배타 처리하고 결과를 함께 배타 처리하는 것입니다. 이 솔루션은 선형 시간으로 실행되며 오버 플로우 할 수 없습니다.
는 여기에 몇 가지 코드가

public class Main { 
    public static int missingno(int[]first,int[]second) { 
     int xor_val = 0; 
     for (int i : first) 
      xor_val ^= i; 
     for (int i : second) 
      xor_val ^= i; 
     return xor_val; 
    } 
    public static void main(String[] args) { 
     int[]a= {1,2,3,4,5,6,7,8}; 
     int[]b = {5,4,6,8,3,2,1}; 
     System.out.println(missingno(b,a)); 
    } 
} 

XOR은 매우 다양한 연산자 기억 증명하는 것입니다. 그것은 교환 가능하고 결합 적이므로 임시 변수없이 변수를 교환하는 데 사용할 수 있습니다.

또 다른 해결책은 목록에 없을 수있는 숫자로 초기화 된 해시 맵을 유지하는 것입니다. 1- 짧은 목록을 살펴보고, 각 값을 기존대로 표시 한 다음 살펴 봅니다. 전체 목록. 설정되지 않은 값이 있으면 누락 된 요소를 발견했습니다. 이것의 장점은 누락 된 요소의 색인을 즉시 알려줍니다.