s*******3
发帖数: 6 | 1 Given a matrix, each cell having only 0's or 1's, find the largest sub-
matrix with equal number of 0's and 1's in it.
求指导！ |
f*****u
发帖数: 308 | 2 这题目测应该用dp吧。回头写个代码看看。
【在 s*******3 的大作中提到】
: Given a matrix, each cell having only 0's or 1's, find the largest sub-
: matrix with equal number of 0's and 1's in it.
: 求指导！
|
C********e
发帖数: 492 | 3 暂时想到用dp，时间复杂度O((mn)^2)
求更好的算法。。
【在 s*******3 的大作中提到】
: Given a matrix, each cell having only 0's or 1's, find the largest sub-
: matrix with equal number of 0's and 1's in it.
: 求指导！
|
k*******a
发帖数: 433 | |
z*t
发帖数: 13 | 5 能到O(n*n*m)
跟二维矩阵地最大字段和类似, 先把问题简化到一维数组(x到y行拍扁成一行，也就是
a[col] = sum(m[i][col] for i in range(x,y)) )。a再做个前缀和 a[i] = sum(a[0:
i])
h = y-x+1 矩形的高度。
问题转化为 a[i] - a[j-1] = h*(i-j)/2 ==> a[i] = a[j+1] + h*(i-j)/2
随j递
增 递减 可用类似杨氏矩阵的搜索办法。 |
D*******r
发帖数: 2323 | 6 建一个同size的matrix，先把原matrix里的第一排和第一列copy到新matrix里。
然后其它各点，如果原matrix里是1，到新matrix里，就是1 + min(上方，左方，左斜
上方在新matrix里的值）；如果原matrix里是0，就copy 0到新matrix里。
最后新matrix里最大的那个数，就是所要找的sub-matrix的右下角，这个数，就是
submatrix的size。
复杂度是n*n.
【在 s*******3 的大作中提到】
: Given a matrix, each cell having only 0's or 1's, find the largest sub-
: matrix with equal number of 0's and 1's in it.
: 求指导！
|
x********k
发帖数: 256 | 7 1 1
1 1
这个按你的算法对应的新矩阵是
1 1
1 2
吧？不知道理解的对不对。
【在 D*******r 的大作中提到】
: 建一个同size的matrix，先把原matrix里的第一排和第一列copy到新matrix里。
: 然后其它各点，如果原matrix里是1，到新matrix里，就是1 + min(上方，左方，左斜
: 上方在新matrix里的值）；如果原matrix里是0，就copy 0到新matrix里。
: 最后新matrix里最大的那个数，就是所要找的sub-matrix的右下角，这个数，就是
: submatrix的size。
: 复杂度是n*n.
|
r****7
发帖数: 2282 | 8 http://www.geeksforgeeks.org/largest-subarray-with-equal-number
【在 s*******3 的大作中提到】
: Given a matrix, each cell having only 0's or 1's, find the largest sub-
: matrix with equal number of 0's and 1's in it.
: 求指导！
|
D*******r
发帖数: 2323 | 9 哦，把题目看偏了，以为是要找最大的全是1的sub-matrix，原来是要找最大的0和1数
目相等的sub-matrix。
【在 x********k 的大作中提到】
: 1 1
: 1 1
: 这个按你的算法对应的新矩阵是
: 1 1
: 1 2
: 吧？不知道理解的对不对。
|
s*******3
发帖数: 6 | 10 求问 “问题转化为 a[i] - a[j-1] = h*(i-j)/2 ==> a[i] = a[j+1] + h*(i-j)/2
随j递增递减，可用类似杨氏矩阵的搜索办法。”
转化为一维问题之后如何在O(M)时间内求出最大值。
是
0:
【在 z*t 的大作中提到】
: 能到O(n*n*m)
: 跟二维矩阵地最大字段和类似, 先把问题简化到一维数组(x到y行拍扁成一行，也就是
: a[col] = sum(m[i][col] for i in range(x,y)) )。a再做个前缀和 a[i] = sum(a[0:
: i])
: h = y-x+1 矩形的高度。
: 问题转化为 a[i] - a[j-1] = h*(i-j)/2 ==> a[i] = a[j+1] + h*(i-j)/2
: 随j递
: 增 递减 可用类似杨氏矩阵的搜索办法。
|
|
|
p**p
发帖数: 742 | 11 我写的java code O(m*m*n) 实现：
本质上跟max sub-matrix sum 差不多，就是把二维问题转化为一维。
public int getSubMatrixWithEqual0And1(int[][] matrix) {
int m, n;
if(matrix == null || (m = matrix.length) == 0 || (n = matrix[0].
length) == 0) {
return 0;
}
int overallMax = 0;
for(int i = 0; i < m; i++) {
int[] rowSum = new int[n];
for(int j = i; j < m; j++) {
for(int k = 0; k < n; k++) {
rowSum[k] += matrix[j][k] == 0 ? -1 : 1;
}
int maxSofar = (j-i+1) * getMaxLenWithEqual0And1(rowSum);
if(maxSofar > overallMax) {
overallMax = maxSofar;
}
}
}
return overallMax;
}
private int getMaxLenWithEqual0And1(int[] arr) {
int n = arr.length;
int[] leftSum = new int[n];
Map map = new HashMap();
int max = 0;
for(int i = 0; i < n; i++) {
leftSum[i] = i == 0 ? arr[i] : leftSum[i-1]+arr[i];
if(leftSum[i] == 0) {
max = i+1;
}
if(map.containsKey(leftSum[i])) {
int len = i - map.get(leftSum[i]);
if(len > max) {
max = len;
}
} else {
map.put(leftSum[i], i);
}
}
return max;
} |
C********e
发帖数: 492 | 12 为什么要leftSum[i] == leftSum[j] ?
这意味着i ~ j 之间都是0，并不是要找的subarray啊
【在 p**p 的大作中提到】
: 我写的java code O(m*m*n) 实现：
: 本质上跟max sub-matrix sum 差不多，就是把二维问题转化为一维。
: public int getSubMatrixWithEqual0And1(int[][] matrix) {
: int m, n;
: if(matrix == null || (m = matrix.length) == 0 || (n = matrix[0].
: length) == 0) {
: return 0;
: }
:
: int overallMax = 0;
|
T*****u
发帖数: 7103 | 13 这样的一个社区的必要非充分条件是boundary全部是1或者0，并且boundary不属于除了
这个社区的其他社区。并且这样的社区不是唯一的。照这个思路，先找boundary,然后
一个一个的submap排除试试？ |
p**p
发帖数: 742 | 14 Not sure how you got that from the code.
But the code is there, you probably should try to run it with your example.
【在 C********e 的大作中提到】
: 为什么要leftSum[i] == leftSum[j] ?
: 这意味着i ~ j 之间都是0，并不是要找的subarray啊
|
C********e
发帖数: 492 | 15 你的是对的，我看错了
另外，如果直接进行把你的函数getMaxLenWithEqual0And1()转换到二维，可以O(m * n
)实现，
空间复杂度升到O(m*n)
.
【在 p**p 的大作中提到】
: Not sure how you got that from the code.
: But the code is there, you probably should try to run it with your example.
|
