[ACCEPTED]-O(n) algorithm to find the median of a collection of numbers-median

Accepted answer
Score: 20

There are a number of possibilities. One 14 I like is Hoare's Select algorithm. The basic 13 idea is similar to a Quicksort, except that 12 when you recurse, you only recurse into 11 the partition that will hold the number(s) you're 10 looking for.

For example, if you want the 9 median of 100 numbers, you'd start by partitioning 8 the array, just like in Quicksort. You'd 7 get two partitions -- one of which contains 6 the 50th element. Recursively carry out your 5 selection in that partition. Continue until 4 your partition contains only one element, which 3 will be the median (and note that you can 2 do the same for another element of your 1 choice).

Score: 12

Yes, good puzzle. We can find median developing 23 on the lines you said.

In C we have 1 occurence 22 of max(k), 3 occurrence of next highest, 5 21 of next highest and so on

  1. If we ordered elements 20 of C, number of elements on the left of 19 mth highest number is m^2 (sum of odd numbers)

  2. The 18 numbers that we are interested in (to calculate 17 median) a. If n is odd is (n^2+1)/2 = alpha 16 b. If n is even then alpha1 = n^2/2 and 15 alpha2 = n^2/2+1 but alpha1=n^2/2 is 14 never a square number => the number immediately 13 on the right of alpha1 is equal to alpha1 12 (sum of first m odd numbers is square) => alpha1=alpha2.

  3. So 11 it boils down to determining m such that 10 m^2 (sum of first m odd numbers) is just 9 higher than (n^2/2)

  4. So it boils down to 8 determining m=ceiling(n/sqrt(2) and mth 7 highest number in original sequence. (Whether 6 to find mth highest or (n-m-1)th lowest 5 is optimization).

  5. We can easily find mth 4 highest number (just keep noting first m 3 largest number from left) or use median 2 of medians algortithm to do it in linear 1 time.

Score: 7

Wikipedia has a good article on Selection algorithms. If you 2 are using C++, the STL includes a nth_element() algorithm 1 with linear time on average.

More Related questions