noru0114   3년 전

Heap에서 k번째로 큰 수가 어떤 실수 x보다 큰지/작은지를 판단해야 하는데

worst case O(k) 인 알고리즘이 있을까요?

k번째 큰 값이 정확히 무엇인지는 몰라도되고 x와의 대소비교만 하면 된다는게 힌트라는데 

아무리 생각해도 모르겠네요

chogahui05   3년 전

어떤 문제인가요?

chanten   3년 전

heap은 정렬이 되어 있으니 단순하게 찾으면 안되나요? 모르고 문의드려봅니다.

noru0114   3년 전

네 단순하게 후보들을 queue에 넣고 하나씩 보면 O(k)인거같아요

댓글을 작성하려면 로그인해야 합니다.