8
$\begingroup$

My initial algorithm:

  1. Compare element 0 with every other element, keeping track of how many elements are less than it.
  2. Repeat for each element until an element that is greater than exactly (k-1) elements is found.

I assume this would take $O(n^2)$ in the worst case. Can a faster runtime be achieved without sorting the list?

$\endgroup$
10
$\begingroup$

Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection_algorithm

$\endgroup$
  • 2
    $\begingroup$ In particular Median of Medians by Blum et al., 1973, solves the selection problem in worst-case linear time. Probably the most elegant algorithm I've ever seen. $\endgroup$ – quicksort Feb 12 '17 at 15:11
  • 6
    $\begingroup$ Although this answer the question, it is encouraged to make own description, not only a link. $\endgroup$ – Evil Feb 12 '17 at 18:04
3
$\begingroup$

Unfortunately I can't just comment but I have to post it as an answer.

Anyway, you could try to use a min-heap on your unsorted array, you should be able to get a time complexity of O(n+k*logn).

$\endgroup$
  • 3
    $\begingroup$ Unfortunately I can't just comment but I have to post it as an answer. – which was a good thing, since answers like your post do not belong in the comments. Comments are for improving the questions, not for short answers or similar. $\endgroup$ – Wrzlprmft Feb 12 '17 at 9:25
  • 1
    $\begingroup$ Mh, I feel like mine isn't a full-fledged answer to be honest, I haven't given any specifics as to why or how the use of a min heap could bring the time complexity down, that's why I felt like it belonged more in a comment than in an answer $\endgroup$ – Luca Giorgi Feb 12 '17 at 13:31
  • $\begingroup$ It depends on $k$ whether min-heap or max-heap should be used. $\endgroup$ – Evil Feb 12 '17 at 18:03
3
$\begingroup$

The Quickselect algorithm can do that in O(n) average complexity, it is one of the most often used selection algorithm according to Wikipedia.

It is derived from QuickSort and as such suffers from a O(n²) worst case complexity if you use a bad pivot (a problem that can be avoided in practice).

The algorithm in a nutshell: After the pivoting like in QuickSort, only descend into either the lower or the higher side of the array - depending on which of them has the element you're after.

$\endgroup$
2
$\begingroup$

Create a max-heap of size $k$. The invariant is that the heap always contains the $k$ smallest elements observed so far.

  1. Insert the first $k$ elements of the list into the heap
  2. For each remaining element $i$ in the list:
    • let $M$ be the maximum element in the heap
    • If $i < M$, then delete $M$ and insert $i$ into the heap

At the end, the heap will contain the $k$ smallest elements in the list.

Looking up the maximum element has constant cost. The cost of insertion and deletion is $O(k)$. The time complexity of this method is $O(n . \log k)$

$\endgroup$
  • 1
    $\begingroup$ Max-heap or Min-heap, it depends on k > n/2. $\endgroup$ – Evil Feb 12 '17 at 18:45
  • $\begingroup$ @Evil You want to check if i is smaller than any of elements in the heap. So you want to know whether it is smaller than the largest of them. Looking up the maximum element is O(1) in max-heap, but not in min-heap. $\endgroup$ – Behrouz Babaki Feb 12 '17 at 18:49
  • 1
    $\begingroup$ True. Imagine that k=1 or k=n, would you use the same heap in the both cases? Maybe it is possible to use the min-heap somehow when it is faster? (I know it is, you have +1 from me, just a nitpick, do not worry). $\endgroup$ – Evil Feb 12 '17 at 19:02
  • 1
    $\begingroup$ @Evil You're right. I discarded your comment hastily. When k>n/2, one can use a similar method to store the (n-k) largest elements in a min-heap. The elements removed from the heap are what we want. $\endgroup$ – Behrouz Babaki Feb 12 '17 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.