Top k Occurrences with Multiplicity Medium · Array, Divide and Conquer, Sorting, Heap, Quickselect · AMD · Separate selection from ordering
You are given an integer array values and an integer k. Return the k largest values, counting each occurrence of a duplicate as a separate entry. The output must be ordered in nonincreasing (descending) sequence.
To avoid sorting the whole array, use a selection‑based technique: first isolate the k largest elements without ordering them, then sort only those selected k elements. This achieves expected time O(n + k log k) on average, where n = values.length.
Implement largest_k(values: int[], k: int) -> int[].
Follow‑up: After implementing the function, briefly compare the partition‑based selection approach with using a min‑heap of capacity k and with a full sort‑then‑slice method. Discuss situations where each choice is most attractive (e.g., streaming data, very small k, worst‑case pivot behaviour).
Example 1:
Input: values = [12, 15, 12, 7, 15, 3], k = 4
Output: [15, 15, 12, 12]
Explanation: The four largest numbers are 15 (appears twice) and 12 (appears twice), sorted descending.
Example 2:
Input: values = [-5, -1, -3, -10, -1], k = 2
Output: [-1, -1]
Example 3:
Input: values = [100], k = 0
Output: []
Constraints:
0 <= values.length <= 1500000 <= k <= values.lengthk = 0, return an empty array.k = len(values), return all elements sorted descending.