search

YuezhenQin / javase

Implement Data Structures and Algorithms (Sorting, Searching, Greedy, DP) from Sketch
2 stars 1 forks source link

Top K, Select K: PrioirtyQueue #22

Closed YuezhenQin closed 10 months ago

YuezhenQin commented 10 months ago
YuezhenQin commented 6 months ago

One common type of interview problem is one that asks you to find the k best elements, with "best" being defined by the problem.

The first and easiest way to solve these problems is to sort the input according to the criteria defined in the problem, and then return the top k elements. This has a time complexity of O(n⋅logn) if n is the length of the input.

Using a heap, we can instead find the top k elements in O(n⋅logk). Logically, k < n, so this is an improvement. Practically, because log is so fast anyway, it probably isn't a big deal in terms of a speed increase.

YuezhenQin commented 6 months ago

Solution347. top k frequent elements

Using minHeap to pop minimum

YuezhenQin commented 6 months ago

Solution658. top k closest elements

Using maxHeap to pop maximum