VB.NET 배열 교차점

Question

이것은 대단히 사소 할 수 있지만 n^2 시간 미만으로 실행되는 대답을 찾는 데 문제가 있습니다. 두 개의 문자열 배열이 있고 두 배열에 어느 문자열이 있는지 알고 싶다고합시다. VB.NET 또는 에서 어떻게 효율적으로 그렇게 할 수 있습니까? 이중 루프 이외의 다른 방법은입니까?

Answer 1

간단한 방법 (.NET 3.5가 없다고 가정)은 해시 테이블의 한 배열에서 문자열을 덤프 한 다음 해시 테이블을 검사하는 다른 배열을 반복합니다. 그것은 n^2 검색보다 훨씬 빠릅니다.

Answer 2

두 목록을 모두 정렬하십시오. 그런 다음 목록 A의 다음 항목이 '자갈'이고 목록 B의 다음 항목이 '확실한'경우 '자갈'이 목록 B에 없음을 알 수 있습니다. 포인터/카운터를 목록에 올려 놓기 만하면됩니다 순위가 낮은 결과와 순위를 올립니다.

목록 1 : D, B, M, A는, I는
목록 2 : I는 A는, P는, N은, D, G

정렬 :

목록 예컨대

1 : A, B, D, I, M
목록 2 : A, D는, G, 난, N, P

는 A A 대 -> 경기가 점포 A는, D 대 모두
B 전진 - -> B D 대 D -> 일치, s D, 나는 G 대 모두
발전을 찢어 -> 난> G는 2
발전을 나는 나는 대 -> 경기, 저장 I는, 사전에 모두
M N 대 -> M 목록 1은 더 이상 항목이 없습니다 , 그만. 경기의
목록 I

이 목록은 O를 정렬, A, D이다 (N 로그 (N)), 플러스 O는 (n)이 비교가이 O 수 (N (로그 (N)를 + 1)).

Answer 3

배열 중 하나는 내부 루프에서에 이진 검색을 할 수있는 정렬 된 경우 두 배열을 정렬 할 경우, 이것은 당신이 다음에 한 번에 각을 통해 걸을 수, O(n log n)

Answer 4

에 시간을 감소 일치하는 모든 문자열을 찾으십시오.

의사 코드 :

while(index1 < list1.Length && index2 < list2.Length) 
{ 
    if(list1[index1] == list2[index2]) 
    { 
     // You've found a match 
     index1++; 
     index2++; 
    } else if(list1[index1] < list2[index2]) { 
     index1++; 
    } else { 
     index2++; 
    } 
} 

그럼 당신은 정렬을 수행하는 데 걸리는 시간으로 감소했습니다.