Медиана областей, указанных в матрице

Question

Учитывая матрицу (n x n) из 1 и 0, где 1 представляет землю, а 0 - воду. Как наиболее эффективно найти медиану площади земель?

Например:

1 1 0 0 0

1 0 0 1 1

1 0 1 0 0

Есть три острова, площадь их [1,2,4] и медиана 2

Остров может состоять из непрерывных недиагональных ячеек, содержащих 1: Например:

1 0 1

0 1 0

эта матрица содержит три острова областей [1,1,1]

Мое решение - найти рекурсивно области и затем отсортировать их, чтобы найти медиану, которая занимает O (n ^ 2log (n ^ 2)), есть ли более эффективный способ сделать это?

Answer 1

Использование несвязанного множества дает вам O (A (N)), где A - обратная функция Аккермана, чтобы найти острова, затем используйте nth_element (он же IntroSelect ), чтобы найти N / 2 в O (N), чтобы найти медиану.

sets = DisjointSet(matrix)
median = nth_element(sets, N/2)

Для общего количества O (A (N)) намного меньше, чем O (N ^ 2)

Answer 2

Первый шаг, рекурсивно запустить DFS на сетке и обнаружить все острова и вычислить области за O(n^2) время.

Второй шаг. Вы можете использовать алгоритм Медиана медиан для вычисления медианы массива несортированных островных областей в ожидаемое O(m) время, где m - количество островков.

Общая сложность времени O(n^2).

Если вам нужна дополнительная помощь, я могу предоставить мою реализацию.