Let's say the range of elements is 1 to X. Then take an array of size X and store the counts of elements of this array. As all elements have count 1, the middle marked element is the median. Now loop k/2 to the left and right side of this median index. Complexity: O(n) for storing counts, then O(n) for looping k/2 on both sides, hence overall complexity is O(n).

First find the median using nth_element. Then replace each value V by |V-median|. Call again nth_element for the k-th largest new value, let's denote it by X. Now you can identify the wanted elements — those for which the new value is <= X.