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

How to find median on unsorted matrix?
Автор MODDI, история, 21 месяц назад, По-английски

We have an N*N matrix, can we achieve better than transposing the matrix into an array, and then sorting it?

I did some online searching and found that quickselect eliminates the log factor, how can we extend quickselect to 2 dimensions?

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

»
21 месяц назад, # |
← Rev. 3   Проголосовать: нравится +38 Проголосовать: не нравится

Convert the matrix to an array first, then use nth_element(x,x+n/2,x+n). The overall complexity is the same as the input complexity, which has reached the lower bound.

nth_element is $$$\Theta(n)$$$.

→ Ответить
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится -32 Проголосовать: не нравится

    nth_element is $$$O(n) $$$, not $$$\Theta(n)$$$

    → Ответить
    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      You're wrong, it's $$$\Theta(n)$$$, because it takes at least a linear perusal of all the elements to determine the value of the nth.

      → Ответить
»
21 месяц назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

Just use the Thanos algorithm: among $$$n^2$$$ elements of the matrix, select random $$$n$$$ and find their median with nth_element ;-)

→ Ответить
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How can we efficiently select n random elements from the matrix without iterating over the full matrix?

    → Ответить
  • »
    »
    21 месяц назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    And let's we want to extend the program, and find the smallest median among every submatrix of size K*K, how can we solve this?

    → Ответить
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by MODDI (previous revision, new revision, compare).

→ Ответить