MODDI's blog

How to find median on unsorted matrix?
By MODDI, history, 22 months ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
22 months ago, # |
← Rev. 3   Vote: I like it +38 Vote: I do not like it

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)$$$.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      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.

      → Reply
»
22 months ago, # |
  Vote: I like it -21 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      binary search

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        With binary search wouldnt it be N^2*K*logK, but can we achieve N^2*K or better?

        → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply