Pergunta de entrevista da empresa TuSimple: How to get the k smallest element in O(klogk) time

TuSimple

How to get the k smallest element in O(klogk) time

Sigiloso

21 de mai. de 2018

do you mean O(nlogn)? where n is size of array?

Sigiloso

27 de jan. de 2019

To find k smallest elements among n elements in total, efficient implementation takes O(n logk), using a binary heap of size k.

Sigiloso

18 de out. de 2018

I think it was nlogn, otherwise if k = 1, O(1) seems impossible for unsorted array