S를 배열에 저장된 n 개의 정수 집합 (반드시 정렬 할 필요는 없음)이라고합시다. S에서 10 개의 가장 큰 정수를 찾는 알고리즘을 설계하십시오 (정수를 저장하는 길이가 10 인 별도의 배열을 작성하여). 알고리즘은 O (n) 시간에 끝나야합니다.O (n) 시간 배열에서 10 개의 가장 큰 정수 찾기
필자는 카운트 정렬을 사용하고 마지막으로 10 개의 요소를 새 배열에 추가하여이 문제에 대한 답을 찾을 수 있다고 생각했습니다. 그러나 분명히 이것은 잘못된 것입니다. 누구든지 더 나은 방법을 알고 있습니까?
방법 1 : 당신은 O(N)의 최대 수를 찾아 당신이 10 시간을 사용하는 경우 FindMax() 알고리즘을 사용할 수 있습니다
10 * O(N) =O(N)
당신이 최대 납입을 찾을 때마다 당신이에 넣어
는 CA : 새로운 배열을 당신은 당신이 FindMax();
방법 2 그것은 다음 번을 무시합니다 n 개의 사용 버블 10 회 :
1) Modify Bubble Sort to run the outer loop at most 10 times.
2) Save the last 10 elements of the array obtained in step 1 to the new array.
10 * O(N) =O(N)
방법 3 :
당신은 MAX Heap 사용할 수 있습니다
1) Build a Max Heap in O(n)
2) Use Extract Max 10 times to get 10 maximum elements from the Max Heap 10
* O(logn)
O(N) + 10 * O(logN) = O(N)
사용 order statistic 알고리즘은 10 가장 큰 요소를 찾을 수 있습니다. 다음으로 배열을 반복하여 그보다 작거나 같은 모든 요소를 찾습니다.
TimeComplexity :
http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
그들은 언급 여섯 개 메소드 일단 => O (N) 배열이 반복되는 위해서는 통계 + O (N)
그 최악의 경우는 거의 O (N^2) –
@OneManCrew 최악의 경우는 O (n)입니다. http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf –
방문일 O (N) 이.
균형 이진 트리에 삽입하십시오. O (N) + O (1g2 N).
새 배열에 처음 10 개의 숫자를 추가하십시오. 그런 다음 나머지 요소를 스캔하고 새 배열을 계속 업데이트하십시오. –
쉽게, 감사합니다! – 101ldaniels
기다려주세요.이 작업이 확실하지 않습니까? – 101ldaniels