Given 2 dimensional sorted array(Both row and column wise sorted) write a efficient algo to find median.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Given 2 dimensional sorted array(Both row and column wise sorted) write a efficient algo to find median.
Name |
---|
Looks very similar to finding k-th element of two sorted arrays, which I've seen at TC forums.
Use binary search over the value of the median. Complexity would be O(Rlog(C) log(MaxVal)).
Guess it can be done in a better way since this way you wouldn't use the fact that the columns are sorted.
It seems there is an O(n) algorithm to this problem.