비교 알고리즘

Question

비슷한 차이가있는 유사한 데이터가 포함 된 2 개의 배열 (A 및 B)이 있습니다. A에만있는 객체 배열과 B에있는 객체 배열을 반환하고 싶습니다. 지금까지 내가왔다 생각 : 몇 가지 최적화와

1. 브 루트 포스 (이것은 사소한)
2. 정렬은 배열과 이진 검색을 사용합니다.

다른 옵션에는 어떤 것이 있습니까? 모든 언어/솔루션은 공정한 게임입니다.

Answer 1

두 배열을 모두 정렬 한 다음 두 배열을 동시에 선형 스캔 할 수 있습니다. 이것은 정렬을위한 O (nlogn) 알고리즘과 새로운 배열의 스캔/빌드를위한 O (n) 알고리즘이 될 것입니다.

Answer 2

세트를 사용해보세요. 그들은 대개 difference() 메서드 (또는 이와 비슷한 함수)를 가지고있어 원하는 것을 정확히 반환합니다. 그처럼 간단합니다. 언어에 구애받지 않고 세트를 생성하거나 차이점을 배열로 변환하는 방법은 일반적인 방법을 사용하여 수행됩니다.

Set A = createSetA(); 
Set B = createSetB(); 

Array onlyAElements = transformToArray(A.difference(B)); 
Array onlyBElements = transformToArray(B.difference(A)); 

또는 두 배열을 모두 정렬하고 동시에 두 개의 차이 배열을 가져올 수 있습니다. 예 :

int aIndex = 0; 
int bIndex = 0; 

Array aOnly = new Array(); 
Array bOnly = new Array(); 

while (aIndex != a.length || bIndex != b.length) 
{ 
    if (A[aIndex] == B[bIndex] 
    { 
     aIndex++; 
     bIndex++; 
    } 
    else if (A[aIndex] > B[bIndex]) 
    { 
     aOnly.add(A[aIndex]); 
     aIndex++; 
    } 
    else 
    { 
     bOnly.add(B[bIndex]); 
     bIndex++; 
    } 
} 

한계를 벗어나는 데 몇 가지 실수가 있음을 염두에 두어야합니다. 그러나 코드는 주요 아이디어를 얻는 것입니다.

Answer 3

내가 이미 말한 무슨 이상 구현 또는 알고리즘을 가지고 있지 않지만 나는이 질문을 찾을 수있는 사람을위한 C#을/LINQ에서이 솔루션을 떠날 생각이하고 싶어 :

var a = new int[] { 1, 2, 3, 6, 7, 8, 9, 10 }; 
    var b = new int[] { 1, 2, 3, 4, 5, 6, 7 }; 

    int[] addedToA = a.Except(b); 
    int[] missingFromA = b.Except(a); 

    foreach (var i in addedToA) 
    { 
     Console.Write("{0} ", i); 
    } 
    Console.WriteLine(); 
    foreach (var i in missingFromA) 
    { 
     Console.Write("{0} ", i); 
    } 

을 이 인쇄물은 다음과 같습니다.

8 9 10 
4 5 

Answer 4

많은 정보는 보유하고있는 데이터 유형에 따라 다릅니다. 당신은 정렬을 언급합니다, 그래서 나는 그것을 가지고 있습니다. 크기가 m 및 n 인 세트는 으로 정렬되며 그 크기가 우선합니다. (Asymptotically, 당신이 이진 검색을 수행하거나 두리스트를 걸어 가면 상관 없습니다. 두리스트 모두를 걷는 것은 O(m + n)이되어야합니다.) 물론 radix-sort가있는 정수처럼 더 좋은 정렬 알고리즘을 가진 데이터를 사용한다면 O(m + n)으로 내려갈 수 있어야합니다.

집합을 사용하면 (다른 사람들이 제안한대로) 해시 사용이 암시 적으로 제안되므로 문제가 쉽게 해결됩니다. A (O(m))의 모든 요소를 ​​해시하고 모든 해시를 메모리에 해시 세트로 저장 한 다음 해시 B (O(n))를 해시 집합에서 충돌이 발생할 수있는 위치를 탐지합니다. 이것은 최적화를위한 문제가됩니다. 고전적인 속도 메모리 트레이드 오프를 평가해야합니다. 해시 세트가 클수록 충돌 확인이 빨라집니다. 이는 O(m + n)에서 실행됩니다.

모든 입력을 조사해야하기 때문에 질문하는 알고리즘이 적어도 m + n 시간 후에 실행된다는 것을 증명할 수 있다는 점은 주목할 가치가 있습니다.

Answer 5

배열의 A 요소를 해시 테이블에 채우고 B의 요소를 A에서 효율적으로 결정하기 위해 해시 테이블에서 조회를 수행하는 배열 B를 반복합니다.그런 다음 해시 테이블에서 B의 요소를 사용하여 동일한 작업을 수행하고 배열 A를 반복합니다. 전체적으로 O (N)가됩니다.