有一个 ｎ * n的矩形，其中每个元素只可能是0 or 1。比如如下矩阵A：
1 1 0 0
0 0 1 1
1 0 1 0
1 1 0 1其中 A[0][0], A[0][1], A[3][0], A[3][1] 这四个元素恰好是一个长方形的四个角，且每个元素都是1. 因此称这四个元素围成了一个子矩形。
现在需要判断，给定的矩阵A中，判断是否存在这样四个元素，都是1，且恰好围成一个子矩形？
显然，只需要枚举 top-left，还有 bottom-right 就可以确定出这四个元素了。top-left [i1, j1], bottom-right [i2, j2]。伪代码如下：
for i1 <- 0 to n-1
for j1 <- 0 to n-1
for i2 <- i1 + 1 to n-1
for j2 <- j2 + 1 to n-1
check_are_all_one(A[i1][j1], A[i1][j2], A[i2][j1], A[i2][j2])T(n) = O(n^4)
可以只需要枚举 j1, j2, 然后 i 从 0 ~ n-1 扫描一遍就行。
for j1 <- 0 to n-1
for j2 <- j1+1 to n-1
one_pair_count <- 0
for i <- 0 to n-1
if A[i][j1] & A[i][j2] then
one_pair_count <- one_pair_count + 1
if one_pair_count >= 2 then // 只需要出现过两次A[i][j1], A[i][j2]都是1，就可以由他们围成一个矩形
return true
return false时间复杂度为 T(n) = O(n^3)
这个方案可以将复杂度改进为 O(n^2)，但是需要引入辅助空间，mark[n][n]
A矩阵：
1 1 0 0
0 0 1 1
1 0 1 0
1 1 0 1从A的第一行开始往下扫，
Row 1： 1 1 0 0
这里意味着第一列（column 1，简称C1） 和第二列（column 2，简称C2）可以构成一个待求矩形的上边。对应的mark表为：
C1 C2 C3 C4
C1 0 1 0 0
C2 1 0 0 0
C3 0 0 0 0
C4 0 0 0 0如果Row1 是: 1 1 0 1，那么意味着 C1 和 C2，C2 和 C3，C1 和 C3都可以构成矩形的上边。此时对应的mark表为：
C1 C2 C3 C4
C1 0 1 0 1
C2 1 0 0 1
C3 0 0 0 0
C4 1 1 0 0扫描第二行，Row2：0 0 1 1，C3, C4为1，更新 mark[3-1][4-1]=1, mark[4-1][3-1]=1
mark表更新为：
C1 C2 C3 C4
C1 0 1 0 0
C2 1 0 0 0
C3 0 0 0 1
C4 0 0 1 0扫描第三行：Row3： 1 0 1 0, C1,C3为1，更新 mark[1-1][3-1]=1, mark[3-1][1-1]=1
mark表更新为：
C1 C2 C3 C4
C1 0 1 1 0
C2 1 0 0 0
C3 1 0 0 1
C4 0 0 1 0扫描第四行，Row4：1 1 0 1，C1,C2,C4为1，更新mark[1-1][2-1]=1, mark[2-1][1-1]=1, mark[1-1][4-1]=1, mark[4-1][1-1]=1, mark[2-1][4-1]=1, mark[4-1][2-1]=1
mark表更新为
C1 C2 C3 C4
C1 0 2 0 1
C2 2 0 0 1
C3 0 0 0 0
C4 1 1 0 0此时发现 mark[0][1] = 2，即意味着第一列和第二列有两次扫描中，都匹配上了，这样的话，选择第一列和第二列作为矩形的左右列即可，然后从上往下扫一次（O(n)时间），即可求得矩形上下边界
总的时间复杂度分析：
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
class Solution {
public:
void solve() {
int m[][4] = {
{1,1,0,0},
{0,0,1,1},
{1,0,1,0},
{1,1,0,1}
};
vector<vector<int> > matrix;
for (int i = 0; i < 4; i++) {
vector<int> row;
for (int j = 0; j < 4; j++) row.push_back(m[i][j]);
matrix.push_back(row);
}
cout << "check: " << checkHasRectangle(matrix) << endl;
}
bool checkHasRectangle(vector<vector<int> > &matrix) {
int n = matrix.size(); // n*n matrix
vector<vector<int> > mark(n, vector<int>(n, 0)); // mark 2D array
int target_c1 = -1, target_c2 = -1; // target column c1, column c2 boundary
int target_r1 = -1, target_r2 = -1; // target row r1, row r2 boundary
for (int i = 0; i < n; i++) {
vector<int> hold; // to hold the column index whose value at this row is 1
for (int j = 0; j < n; j++) if (matrix[i][j]) hold.push_back(j);
for (int j1 = 0; j1 < hold.size(); j1++) {
for (int j2 = 0; j2 < hold.size(); j2++) {
if (j1 != j2) mark[hold[j1]][hold[j2]] ++;
// get the result
if (mark[hold[j1]][hold[j2]] >= 2) {
target_c1 = hold[j1], target_c2 = hold[j2];
// go to find up and bottom boundary.
for (int k = 0; k < n; k++) {
if (matrix[k][target_c1] & matrix[k][target_c2]) {
if (target_r1 == -1) target_r1 = k;
else target_r2 = k;
}
}
// cout
printf("Four elements: (%d,%d), (%d,%d), (%d,%d), (%d,%d)\n",
target_r1, target_c1, target_r1, target_c2,
target_r2, target_c1, target_r2, target_c2);
return true;
}
}
}
}
return false;
}
};
int main() {
Solution solution;
solution.solve();
return 0;
}原文：http://blog.csdn.net/nisxiya/article/details/46235945