[ACCEPTED]-O(n) algorithm to find the median of a collection of numbers-median
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).
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
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)
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.
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)
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).
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.
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
We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.