Блог пользователя unemployed

Find Median in 2-d sorted array(sorted in both order column and row wise)?
Автор unemployed, 12 лет назад, По-английски

Given 2 dimensional sorted array(Both row and column wise sorted) write a efficient algo to find median.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить