0
$\begingroup$

If we have length $n$ unsorted array such that each element is integer and different, how to find $i$ largest numbers in linear time O(n)? but $i \leq n^{\frac{1}{2}}$.

For example, if we have $A = [11, 6, 8, 1, 9, 100, 88]$ and input $i = 2$, then output is $[100, 88]$ (sorted).

$\endgroup$
2
$\begingroup$

Use a selection algorithm to find the $i$th largest number. This can be done in linear time. Then, do a second scan over the array to find all numbers larger than the $i$th largest number. (With many selection algorithms, this last step is unnecessary, as they partition the array into elements smaller than the $i$th largest and larger than the $i$th largest.)

$\endgroup$
4
  • $\begingroup$ How can I apply this algorithm to this finding multiple largest numbers problem? $\endgroup$ – t24akeru Mar 27 at 2:37
  • $\begingroup$ @t24akeru, see edited answer. You should be able to work out the details from here. $\endgroup$ – D.W. Mar 27 at 5:58
  • $\begingroup$ @D.M. Thank you! One question, is the scanning operation not counted time complexity? $\endgroup$ – t24akeru Mar 27 at 6:24
  • 1
    $\begingroup$ I would like to add that the classical selection algorithms (quickselect / median of medians) both partition the array so that the largest $i$ elements are also the last elements if you select on the $i$th element. $\endgroup$ – orlp Mar 27 at 6:36

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.