I have got some difficulties to solve this algorithm problem.
I have been given a set of n points on a number line. Those points are not sorted in the set. For any two points $(a, b)$ in the set, their distance is calculated as $|a-b|$. Now I need to calculated the kth largest among all possible distances of the n points in $O(n \log n)$ time using a randomized algorithm and a deterministic algorithm respectively.
To solve this problem, I begin with sorting the n points in $O(n \log n)$ time. I noticed that this problem it is similar to the quick select for the kth largest of the array. The naive approach is to calculate all possible distances and do quick select. But this takes $O(n^2)$ running time. It seems that I have to run the quick select with only necessary distances calculated. Now I have to do two things recursively:
- partition all distances with a randomly chosen pivot, and
- find out the numbers of distances on each side to determine which part for recursion.
There would be $O(n \log n)$ steps for the recursion. So, I have to do the two things above in $O(n)$ time. And I have difficulties with that.
Please help me. Thank you very much.