mxn给定一个仅包含 0 和 1 的大小矩阵。我需要找到其中包含相同数量的 1 和 0 的最大子矩阵。蛮力方法是O(m^2*n^2)我们能做得比这更好吗？
我尝试应用动态编程，但找不到任何最佳子结构。
我相信这里讨论了这个问题的类似一维版本：
Space-efficient algorithm for find the maximum balance subarray?
它有一个O(n)使用一些额外空间的解决方案。
问问题
2170 次
4 回答
5
该算法假设我们搜索具有连续行和列且具有最大可能的高度和宽度乘积的子矩阵。
从以下预处理开始：
A = substitute_zero_with_minus_one(InputMatrix)
B = prefix_sum_for_each_column(A)
C = prefix_sum_for_each_row(B)
现在对每对行 (i, j) 执行以下操作：
for each column k:
d = C[k, j] - C[k, i]
if h[d] not empty:
if (k - h[d]) * (j - i) is greater than best result:
update best result
else:
h[d] = k
时间复杂度为 O(N 2 * M)，额外空间为 O(N * M)。
于 2012-12-04T10:05:29.713 回答
1
我们假设 m < n，我们可以有一个 O(M * M * N) 算法。如果我们将所有 0 替换为 -1，我们只会找到总和为 0 的最大 submaxtrix。
- 获取每行中段的总和（i，j），我们定义它们c1，c2，c3....，cn，我们可以通过您引用的算法对其运行O（n）算法。
- 我们应该执行步骤 1 M * M 次以获得最大的 submaxtrix，其和为 0，因此复杂度为 O(M * M * N)。
于 2012-12-04T09:31:50.903 回答
1
我假设仅使用原始矩阵的连续行\列形成子矩阵（即通过删除第一行或最后一行或列）。
这样，一个矩阵可以表示为
Mat = {origin(row,col), rowCount, columnCount}
如果原始矩阵的维度为 M x N，则
rowCount = M - row
columnCount = N - col
Mat = {origin(row,col), M - row, N - col}.
变量row和col分别具有可能的值M，N这意味着存在O(MxN)这样的矩阵。
算法理念
(m, n)从队列中弹出矩阵- 测试 。如果成功，输出矩阵
- 构造所有矩阵
(m, n-1)并(m-1, n)放入队列 - 回到 1。
现在有两点：
- 当您减少维度时，只有 4 个可能的矩阵（2 个通过删除行，2 个通过删除列）
- 您通过删除第一行和最后一行\列来构造一个子矩阵。您只需要删除您删除的行\列的计数，这需要
O(n)时间O(m)。这是动态规划步骤。
这意味着复杂性是O(max(M,N)MN)
于 2012-12-04T10:13:46.767 回答
1
我创建了一个演示搜索算法优化的小应用程序。请让我知道这是否是您正在寻找的。
笔记：
- 程序创建一个方阵
- 为了便于阅读，我使用集合来处理数据。我认为处理过程中存在过载，但我只是想指出原理。
这里是：
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Program
{
class Matrix
{
public int[][] JaggedInteger2DMatrix { get; set; }
public List<MatrixCell> Cells { get; set; }
public List<MatrixLine> Lines { get; set; }
public int Width { get; set; }
public int Height { get; set; }
public Matrix(int size, int seed)
{
var r = new Random(seed);
int[][] jaggedInteger2DMatrix = new int[size][];
for (int i = 0; i < size; i++)
{
jaggedInteger2DMatrix[i] = new int[size];
for (int j = 0; j < size; j++)
{
jaggedInteger2DMatrix[i][j] = r.Next(2);
//Console.Write(jaggedInteger2DMatrix[i][j]+" ");
}
//Console.Write("\r\n");
}
InitializeMatrix(jaggedInteger2DMatrix);
}
public Matrix(int[][] jaggedInteger2DMatrix)
{
InitializeMatrix(jaggedInteger2DMatrix);
}
private void InitializeMatrix(int[][] jaggedInteger2DMatrix)
{
JaggedInteger2DMatrix = jaggedInteger2DMatrix;
Height = jaggedInteger2DMatrix.GetLength(0);
Width = jaggedInteger2DMatrix[0].GetLength(0);
Cells = new List<MatrixCell>();
Lines = new List<MatrixLine>();
int horizontalLineCounter = 0;
MatrixCell matrixCell = null;
foreach (var horizontalLine in jaggedInteger2DMatrix)
{
int verticalLineCounter = 0;
foreach (var cell in horizontalLine)
{
matrixCell = new MatrixCell()
{
HorizontalLineIndex = horizontalLineCounter,
Value = cell,
VerticalLineIndex = verticalLineCounter
};
Cells.Add(matrixCell);
if (Lines.Where(line => line.LineType == Line.Vertical && line.LineIndex == verticalLineCounter).Count() == 0)
{
var line = new MatrixLine()
{
LineType = Line.Vertical,
LineIndex = verticalLineCounter
};
Lines.Add(line);
}
Lines.Where(line => line.LineType == Line.Vertical && line.LineIndex == verticalLineCounter).FirstOrDefault().Cells.Add(matrixCell);
if (Lines.Where(line => line.LineType == Line.Horizontal && line.LineIndex == horizontalLineCounter).Count() == 0)
{
var line = new MatrixLine()
{
LineType = Line.Horizontal,
LineIndex = horizontalLineCounter
};
Lines.Add(line);
}
Lines.Where(line => line.LineType == Line.Horizontal && line.LineIndex == horizontalLineCounter).FirstOrDefault().Cells.Add(matrixCell);
verticalLineCounter++;
}
horizontalLineCounter++;
}
}
}
class MatrixCell
{
public int Value { get; set; }
public int VerticalLineIndex { get; set; }
public int HorizontalLineIndex { get; set; }
}
class MatrixLine
{
public Line LineType { get; set; }
public int LineIndex { get; set; }
public List<MatrixCell> Cells { get; set; }
public MatrixLine()
{
Cells = new List<MatrixCell>();
}
}
enum Line
{
Horizontal,
Vertical
}
private static void Search(Matrix matrix, bool optimizeCellCount, out IEnumerable<MatrixCell> optimizedSelection, out int iterations)
{
optimizedSelection = null;
var count = 0;
iterations = 0;
for (int i = 0; i < matrix.Width; i++)
{
for (int j = 1; j <= matrix.Width; j++)
{
var selectedVerticalLines = matrix.Lines.Where(line => line.LineType == Line.Vertical).Skip(i).Take(j);
for (int k = 0; k < matrix.Height; k++)
{
for (int l = 1; l <= matrix.Height; l++)
{
/**
* Here's where the search is optimized
**********************************************************************************************
*/
if (optimizeCellCount)
{
//if the submatrix cell count is smaller than the current count, break the iteration
if (count > Math.Min(Math.Abs(matrix.Height - k), l) * Math.Min(Math.Abs(matrix.Height - i), j))
{
continue;
}
}
/*
**********************************************************************************************
*/
iterations++;
var selectedHorizontalLines = matrix.Lines.Where(line => line.LineType == Line.Horizontal).Skip(k).Take(l);
var horizontalCells = selectedHorizontalLines.Aggregate<MatrixLine, List<MatrixCell>>(new List<MatrixCell>(), (a, b) =>
{
a.AddRange(b.Cells);
return a;
});
var verticalCells = selectedVerticalLines.Aggregate<MatrixLine, List<MatrixCell>>(new List<MatrixCell>(), (a, b) =>
{
a.AddRange(b.Cells);
return a;
});
var cells = horizontalCells.Intersect(verticalCells);
if (cells.Count() > count)
{
var sum = cells.Sum(t => t.Value);
var cellsCount = cells.Count();
if (sum != 0)
{
if (cellsCount / (double)sum == 2)
{
//match
optimizedSelection = cells;
count = cellsCount;
}
}
}
}
}
}
}
}
private static float GetLineCost(int width, int startPosition, int length)
{
float cost = 0;
for (int i = startPosition; i < length; i++)
{
cost += Math.Min(Math.Abs(width - i), i + 1);
}
return cost;
}
static void Main(string[] args)
{
Matrix matrix = new Matrix(20, 1);
bool optimizeCellCount = true;
IEnumerable<MatrixCell> optimizedSelection;
int iterations;
var watch = new System.Diagnostics.Stopwatch();
//optimized search
watch.Start();
Search(matrix, optimizeCellCount, out optimizedSelection, out iterations);
watch.Stop();
Console.WriteLine("Full Optimized Search");
Console.WriteLine("position: [{0},{1}],[{2},{3}] size : {4} search time : {5} iterations: {6}",
optimizedSelection.Min(cell => cell.VerticalLineIndex),
optimizedSelection.Min(cell => cell.HorizontalLineIndex),
optimizedSelection.Max(cell => cell.VerticalLineIndex),
optimizedSelection.Max(cell => cell.HorizontalLineIndex),
optimizedSelection.Count(),
watch.Elapsed,
iterations
);
watch.Reset();
//no optimization
watch.Start();
Search(matrix, !optimizeCellCount, out optimizedSelection, out iterations);
watch.Stop();
Console.WriteLine("Non-Optimized Search");
Console.WriteLine("position: [{0},{1}],[{2},{3}] size : {4} search time : {5} iterations: {6}",
optimizedSelection.Min(cell => cell.VerticalLineIndex),
optimizedSelection.Min(cell => cell.HorizontalLineIndex),
optimizedSelection.Max(cell => cell.VerticalLineIndex),
optimizedSelection.Max(cell => cell.HorizontalLineIndex),
optimizedSelection.Count(),
watch.Elapsed,
iterations
);
watch.Reset();
//Console Output:
/***************************************************************************************
* Full Optimized Search
* position: [9,1],[18,19] size : 190 search time : 00:00:02.3963657 iterations: 19108
* Non-Optimized Search
* position: [9,1],[18,19] size : 190 search time : 00:00:05.8385388 iterations: 160000
****************************************************************************************/
}
}
于 2012-12-04T15:54:45.013 回答