4 ms·
Doesn't this only work if the elements are unique? say you wanted the top three from [1,2,3,2,3,3,4,3,3,3,3,4,3], then the kth largest element would be 3, and w
by axman6 15y ago
Doesn't this only work if the elements are unique? say you wanted the top three from [1,2,3,2,3,3,4,3,3,3,3,4,3], then the kth largest element would be 3, and we'd end up outputting [3,3,3,4,3,3,3,3,4,3], which is obviously not k elements.
- davidtgoldblatt 15y agoFor these types of problems you usually assume that every element is unique. The fix is just making two passes through the array instead of one, so it's still O(n). It's typically easy to reduce solving such a problem with duplicates allowed into a very similar one without duplicates. Just replace every element x by the ordered pair (x, the position in the array where x came from) and then use a modified comparison function that sorts according to the second element in the pair if two ordered pairs are equal in the first element.