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?

Improve this question
$\endgroup$
2

4 Answers 4

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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
    Commented Feb 12, 2017 at 15:11
  • 7
    $\begingroup$ Although this answer the question, it is encouraged to make own description, not only a link. $\endgroup$
    – Evil
    Commented Feb 12, 2017 at 18:04
5
$\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).

Improve this answer
$\endgroup$
3
  • 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
    Commented Feb 12, 2017 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
    Commented Feb 12, 2017 at 13:31
  • $\begingroup$ It depends on $k$ whether min-heap or max-heap should be used. $\endgroup$
    – Evil
    Commented Feb 12, 2017 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.

Improve this answer
$\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)$

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Max-heap or Min-heap, it depends on k > n/2. $\endgroup$
    – Evil
    Commented Feb 12, 2017 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
    Commented Feb 12, 2017 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
    Commented Feb 12, 2017 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
    Commented Feb 12, 2017 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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