두 개의 정수 배열 중에서 가장 긴 교차점을 찾습니다.

Question

이 문제가 있지만 시간 복잡성과 공간 복잡성의 관점에서 문제를 해결하는 가장 좋은 방법을 모릅니다. 나는 두 개의 정수 배열

a={1,2,3,4,5} 
    b={2,3,4,5,6} 

이 물론 그들이 반드시 정렬 할 가정 .

그래서 질문은 2,3,4,5를 찾는 방법입니까? 몇 가지 코드를 작성하는 것이 좋습니다. 미리 감사드립니다.

Answer 1

이것은 실제로 꽤 인기있는 프로그래밍 문제입니다. 이를 해결하기위한 동적 프로그래밍 방식이 있습니다. 자세한 내용은 http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Answer 2

여기서 확인할 수 있습니다. 왜 DP가 필요한가요? 질문은 교차로가 아니라 가장 긴 교차로를 찾습니다. 내가 놓친 점이 있니?

많은 해결책이 있습니다.

하나의 배열을 사전에 저장할 수 있으며 다른 배열의 각 요소에 대해 사전을 검사 할 수 있습니다. 그게 O(n). 이것은 사전으로 인해 더 많은 공간이 필요합니다. 그리고 그것은 제자리에 없습니다.

다른 해결책은 a의 각 요소에 대해 b에 대한 선형 검색을 수행 할 수 있습니다. 당신이 두 배열을 모두 정렬하는 경우, 또 하나가 될 것입니다. O(n.m)

그런 다음 한 배열의 각 요소에 대해 다른 배열의 이진 검색을 수행하십시오. 당신은 2의 교차점을 발견 할 것이다. 이것은 mlogn + nlogn 또는 nlogm + mlogm

여기에 DP가 필요합니까?

Answer 3

이 링크가 문제를 해결할 수 있기를 바랍니다. 공통 기능을 써야합니다. 두 개의 배열에 공통 번호가 표시됩니다. 그리고 루프에 대해서만 을 사용합니다. 왜 복잡성이 단지 O (N)이 될지 왜 생각하십니까?

Find common numbers.

코드는 C입니다. 하지만 당신이 그 논리를 이해할 수 있기를 바랍니다.

Answer 4

처음에 배열을 정렬해야하며, 두 번째로이 배열의 교차점을 찾기 위해 이진 검색을 사용해야합니다. 왜? 왜냐하면 만약 우리가 정렬없이 교차를 검색한다면, 우리의 알고리즘 노력은 N^2이 될 것이지만, 검색 전에 배열을 정렬한다면 totaly는 [log_2(N)N + (N(log_2(N)) up to N^2)]이 될 것입니다. 내 방법은 대부분의 샘플에 유용합니다