Solution to nu2011 (Double-Median) by codility

5 Mar


Question Name: nu2011 or DoubleMedian

For the given queries, we need to find the median in two sorted arrays of different lengths. Then we need to find out the median of the query results. That is, we need to find the median in an unsorted array. Both of these sub-questions are classic. And you could find tons of articles via Google. For the second sub question, typically we have two methods. One solution is to sort the array and return the element in the middle position. This method could guarantee the time complexity be O(NlogN) in any case. And this is what the official golden solution used.

The other method is quick-select, which is similar with quicksort sorting algorithm. There are many variants of quick-select. And we are using a simple one: quick-select with shuffle. The expected time complexity is O(N). And in the worst case, the time complexity is O(N^2). In practice, it should work quite quickly.

Leave a Reply

Your email address will not be published. Required fields are marked *