O의 90 번째 백분위 수를 계산

Question

이 가능한 중복 (N) 시간 :
Can you sort n integers in O(n) amortized complexity?

내가 정수의 정렬되지 않은리스트에 근거 해, 알고리즘을 쓸 필요는, "가장 낮은 반환 파일의 숫자의 90 % 이상을 초과하는 파일의 숫자 "또는 해당 숫자가 없으면 -1입니다. 간단합니다. 병합 정렬을 사용하여 목록을 정렬 한 다음 색인의 90 %에서 시작하여 그 앞에있는 숫자보다 큰 첫 번째 숫자를 찾습니다.

질문의 2 번 부분은 나를 혼란스럽게 만들었습니다. 우리는 더 많은 정보를 얻었습니다. 정수는 급여를 의미합니다. 즉, 정수는 모두 양수이고, 대다수는 1,000,000 미만입니다. O (n) 시간에 원래의 문제를 해결하는 알고리즘을 작성하는 것이 가능하지만, 이것이 가능한지 조금도 알지 못합니다. 어떤 아이디어?

나는 지금까지 해왔 던 것을 게시 할 것이지만, 나는 무엇이든을 생각해 낼 수 없었다.

Answer 1

배열에서 k 번째로 큰 요소를 선택하는 selection algorithm을 찾고 있습니다. Wikipedia 기사에서는 quicksort와 비슷한 O (n) 알고리즘을 제공하지만 전체 배열을 정렬하지 않으므로 O (n * logn) 런타임을 피할 수 있습니다.

요소가 모두 특정 범위 (예 : 1-1000000)로 묶인 경우 O (n)에서 counting sort 또는 bucket sort을 사용하여 요소를 정렬 한 다음 필요한 요소를 선택하십시오. 이 경우 요소의 "대다수"가 모두가 아닌 1000000 미만이므로 1000001 버킷의 버켓 정렬을 수행하고 1000000 이상의 모든 요소에 마지막 버킷을 사용할 수 있습니다.