给定一个由 1 和 0 组成的矩阵 (n x n)，其中 1 代表土地，0 代表水。
如何以最有效的方式找到土地面积的中位数？
例如:
1 1 0 0 0
1 0 0 1 1
1 0 1 0 0
有3个岛，面积为[1,2,4]，中位数为2
一个岛可以由包含 1 的连续非对角线单元组成:
例如:
1 0 1
0 1 0
该矩阵包含三个区域岛屿 [1,1,1]
我的解决方案是递归查找区域，然后对它们进行排序以找到需要 O(n^2log(n^2)) 的中位数，有没有更有效的方法来做到这一点？
最佳答案
第一步，在网格上递归运行 DFS，并在 O(n^2) 时间内发现所有岛屿并计算面积。
第二步，您可以使用Median of Medians 算法计算未排序岛屿区域数组在预期O(m) 时间内的中值，其中m 是岛屿的数量。
总体时间复杂度 O(n^2) 。
如果您需要进一步的帮助，我可以提供我的实现。
关于algorithm - 矩阵中给出的面积的中位数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52167813/