dubovoy.vladimir
BAN USER@Arun "Median is the middle element in the sorted array of numbers" - sorted array is quite weak assumption
- dubovoy.vladimir February 19, 2013k-th largest element will be definitely located in subset [0..k-1],[0..k-1], as far the rows and columns are sorted, the k-th element is greater than any [0..k-2] element for each row/column.
int max_item = m[k][k];
for(int i = k-1; i >=0; i--)
{
int max1 = max(m[0][i],m[i][0]);
if(max1 >max_item)
max_item = max1;
else break;
}
worst case complexity O(k)
- dubovoy.vladimir February 18, 2013We can find the exact median iterating all he items of incoming set in O(n) time, but if we use some divide-and-conquer approach to achieve a O(log n) time.
An approximate median can be found if we pick randomly N numbers of the sequence and compute the median of this subset.
If we have the sequence of infinite size we can make an induction step. Find median of some big enough N number of items, and find its median m1= f(N), then find median for some extended set N+1 (or better N+K) m2 = f(N+K), if the epsilon e=m1-m2 is small enough we can assume that the median of entire set is m=0.5*(m1+m2)+/-e
- dubovoy.vladimir February 20, 2013