Click here to see the full article post
One potential optimization for Solution #3: since we only care about the median value, we could use "find kth smallest element" to find the median of column in O(N).
C++ STL has nth_element which rearranges the elements in the range in such a way that the element at the nth position is the element that would be in that position in a sorted sequence. So the time complexity of Solution #3 would be O(mn) I think.
AC C++ code in the pic attached.
Yup, you can use the famous selection algorithm to optimize Solution #3 to O(mn), but you don't have to. I mentioned that briefly in Solution #4.
@jonsnow1984 Because when you append elements in
rows, it is already sorted. In other words, you are inserting the row index of every element. For example, you always insert 0's, then insert 1's in
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.