3 ms·
I suspect your parent poster is being facetious (if we fix k, then just keep a buffer of the k largest elements we've seen so far. For any new element we see, c
by davidtgoldblatt 15y ago
I suspect your parent poster is being facetious (if we fix k, then just keep a buffer of the k largest elements we've seen so far. For any new element we see, check if it's larger than the smallest element in the buffer and if so remove the smallest and insert the new one. This takes O(k) time, so the algorithm overall takes O(kn), which, since k is constant, is O(n)).
In fact, this can be done in O(n) time even if k isn't constant: use the selection algorithm to find the k'th largest element (in O(n) time) and then go through the list again and output every number that's k or larger.
- axman6 15y agoDoesn'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.