C#: n x n 행렬에서 가장 큰 m 요소를 찾는 효율적인 알고리즘

Question

N X N 행렬에서 가장 큰 M 요소를 찾기위한 효율적인 알고리즘이 있는지 알고 싶습니다.

double[] greatestValues(double[][] matrix, int numberOfElements);

어떤 아이디어?

Answer 1

N X N 행렬을 N X N 항목 배열로 취급하면 다음 기술 중 하나를 적용 할 수 있습니다.

빠른 정렬 기반 선택 알고리즘의 직접 응용 빠른 정렬 기반 선택 알고리즘을 사용하여 K가 가장 작거나 가장 큰 요소를 찾을 수 있습니다. 가장 작은 요소를 찾으려면 중앙값의 중앙값 빠른 정렬 기반 알고리즘을 사용하여 가장 작은 요소를 찾으십시오. Kth 가장 작은 요소를 찾는 파티션 후, Kth 작은 요소보다 작은 모든 요소가 Kth 요소에 왼쪽으로 존재하고 모든 요소가 더 큰 요소가 Kth 가장 작은 요소에 오른쪽으로 나타납니다. 따라서 1st에서 Kth 요소의 모든 요소는 가장 작은 요소를 구성합니다. 시간 복잡성은 N에서 선형이며 총 요소 수입니다.

데이터 구조 기반 솔루션 또 다른 간단한 방법은 목록의 각 요소를 대부분의 K 요소와 함께 힙 또는 자체 밸런싱 바이너리 검색 트리와 같은 순서 세트 데이터 구조에 추가하는 것입니다. 데이터 구조에 k 요소가 더 많을 때마다 O (log k) 시간에 수행 할 수있는 가장 큰 요소를 제거합니다. 각 삽입 작업은 O (log k) 시간이 소요되므로 전체 O (NLOG K) 시간이 발생합니다.

목록을 θ (n) 시간에 힙으로 변환 한 다음 요소를 우선 순위 대기열에 배치하는 수정 된 너비 우선 검색 알고리즘을 사용하여 힙을 횡단 할 수 있습니다 (일반적으로 사용되는 일반 대기열 대신에 요소를 배치합니다. BFS), 정확히 K 요소를 가로 지른 후 스캔을 종료합니다. 큐 크기가 트래버스 전체에 걸쳐 O (k)로 남아 있으므로 O (Klog K)가 완료되는 데 시간이 필요 하므로이 알고리즘에서 O (N + Klog K)의 시간이 지남에 따라 발생합니다.

에서 여기.