Прямоугольная область в массиве - PullRequest
Новая
       4

Прямоугольная область в массиве

9 голосов
/ 18 сентября 2010

Учитывая N * N матрицу, имеющую 1 и 0 в них, и учитывая целое число k, каков наилучший способ найти прямоугольную область, в которой есть k 1?

Ответы [ 2 ]

3 голосов
/ 18 сентября 2010

Я могу сделать это с O (N ^ 3 * log (N)), но уверен, что лучшее решение быстрее. Сначала вы создаете еще одну N * N матрицу B (исходная матрица A). Логика B следующая: 

B[i][j] - is the number of ones on rectangle in A with corners (0,0) and (i,j).

Вы можете оценить B для O (N ^ 2) путем динамического программирования: B [i] [j] = B [i-1] [j] + B [i] [j-1] - B [i- 1] [j-1] + A [i] [j].

Теперь очень легко решить эту проблему с помощью O (N ^ 4) путем итерации по всем правым нижним частям (i = 1..N, j = 1..N, O (N ^ 2)), слева -низу (z = 1..j, O (N)) и справа-вверху (t = 1..i, O (N)), и вы получите количество единиц в этом прямоугольнике с помощью B: 

sum_of_ones = B[i][j] - B[i][z-1] - B[t-1][j] + B[t-1][z-1].

Если вы получили ровно k: k == sum_of_ones, то получите результат.

Чтобы сделать это N ^ 3 * log (N), вы должны найти правый верхний при бинарном поиске (чтобы не просто перебирать все возможные ячейки).

2 голосов
/ 18 сентября 2010

Рассмотрим эту более простую задачу:

Учитывая вектор размера N, содержащий только значения 1 и 0, найдите подпоследовательность, которая содержит ровно k значений 1.

Пусть A будет заданным вектором, а S[i] = A[1] + A[2] + A[3] + ... + A[i], что означает, сколько единиц в подпоследовательности A[1..i].

Для каждого i мы заинтересованы в существовании j <= i такой, что S[i] - S[j-1] == k.

Мы можем найти это в O(n) с помощью хеш-таблицы, используя следующее соотношение:

S[i] - S[j-1] == k => S[j-1] = S[i] - k

let H = an empty hash table
for i = 1 to N do
  if H.Contains (S[i] - k) then your sequence ends at i
  else
    H.Add(S[i])

Теперь мы можем использовать это для решения вашейзаданная проблема в O(N^3): для каждой последовательности строк в заданной матрице (имеется O(N^2) последовательностей строк), рассмотрите эту последовательность для представления вектора и примените к ней предыдущий алгоритм.Вычисление S немного сложнее в матричном случае, но это не так сложно понять.Дайте мне знать, если вам нужна дополнительная информация.

Обновление: Вот как алгоритм будет работать на следующей матрице, предполагая k = 12: 

0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0

Рассмотримтолько первая строка: 

0 1 1 1 1 0

Считайте, что это вектор 0 1 1 1 1 0 и примените к нему алгоритм для более простой задачи: мы обнаружим, что подпоследовательности не добавляется до 12, поэтому мы идем дальше.

Рассмотрим первые две строки: 

0 1 1 1 1 0
0 1 1 1 1 0

Считайте их вектором 0+0 1+1 1+1 1+1 1+1 0+0 = 0 2 2 2 2 0 и примените к нему алгоритм для более простой задачи: опять же, нет подпоследовательности, которая складывается до 12,поэтому идем дальше.

Рассмотрим первые три строки: 

0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0

Считаем их вектором 0 3 3 3 3 0 и применим алгоритм к более простой задаче: мы находим последовательность, начинающуюсяв положении 2 и заканчивая в положении 5, чтобы быть решением.Отсюда мы можем получить весь прямоугольник с простой бухгалтерией.

...