JavaScript를 사용하여 두 순서 목록의 중앙값 문제를 해결하기 위한 샘플 코드

숫자를 작은 것부터 큰 것 순으로 배열합니다. 이때 가운데 변수 의 값을 중앙값이라고 합니다.

그러면 두 개의 순서 목록이 주어지면 공통 중앙값을 어떻게 찾을 수 있을까요?

이 문제가 발생하면 가장 먼저 생각나는 해결책은 순서가 지정된 두 목록을 병합한 다음 오름차순으로 정렬하고 마지막으로 중앙값을 한 번에 꺼내는 것입니다.

이 접근 방식은 매우 간단하고 편리하지만 정렬로 인해 효율적이지 않으므로 O(N*logN)의 알고리즘입니다.

그렇다면 어떻게 최적화할 수 있을까요?

정렬된 선형 목록을 병합하는 알고리즘을 참조할 수 있습니다:

1. 두 개의 포인터를 사용하여 현재 정렬된 목록을 가리키고 새로운 배열을 사용하여 더 작은 배열 요소의 비교.

2. 두 포인터가 가리키는 배열 요소를 비교하고 더 작은 것을 새 배열에 저장한 후 포인터를 뒤로 이동합니다. 이 프로세스는 포인터 중 하나가 비어 있거나 중앙값이 새 배열에 의해 수신될 때까지 계속됩니다. 그런 다음 중앙값이 직접 반환됩니다.

3.2 단계 이후에 포인터가 null이 아니고 이때 새 배열에서 중간 값을 받지 못한 경우 계속 사용하세요. 정렬된 목록을 순회하는 포인터는 중앙값이 수신될 때까지 이를 반환합니다.

4.최적화된 알고리즘은 O(m+n)으로 효율성이 대폭 향상되었습니다.

아아아아

위 내용은 JavaScript를 사용하여 두 순서 목록의 중앙값 문제를 해결하기 위한 샘플 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!