统计方阵中顶点为1且边平行行列的矩形数量

核心思路 #

轴对齐矩形的四个顶点由两对不同的行和两对不同的列唯一确定。只要某两对列（c1, c2）在至少两行（r1, r2）的位置同时为1，那么(r1,c1)、(r1,c2)、(r2,c1)、(r2,c2)这四个点就构成符合要求的矩形。

对于每一组列对(c1, c2)，统计有多少行满足该行的c1和c2列都是1，记这个数量为k。从k行中任选2行就能组成一个矩形，因此该列对贡献的矩形数为组合数 C(k,2) = k*(k-1)/2。遍历所有列对并累加贡献值，即可得到总数。

基础实现方案 #

步骤

1. 遍历所有不重复的列对（c1 < c2，避免重复计算同一组列的不同顺序）。
2. 对每个列对，逐行检查该行的c1、c2列是否均为1，统计符合条件的行数k。
3. 计算该列对的贡献值k*(k-1)//2，累加到总数中。

Python代码示例

def count_rectangles(matrix):
    if not matrix or not matrix[0]:
        return 0
    row_count = len(matrix)
    col_count = len(matrix[0])
    total = 0
    
    # 遍历所有列对
    for c1 in range(col_count):
        for c2 in range(c1 + 1, col_count):
            valid_rows = 0
            # 统计当前列对下，两行都为1的行数
            for r in range(row_count):
                if matrix[r][c1] == 1 and matrix[r][c2] == 1:
                    valid_rows += 1
            # 累加组合数
            total += valid_rows * (valid_rows - 1) // 2
    return total

# 测试示例矩阵
test_matrix = [
    [1,0,1,1,1],
    [1,1,0,0,1],
    [1,0,1,1,0],
    [0,1,1,1,1],
    [1,0,1,1,1]
]
print(count_rectangles(test_matrix))  # 输出：8

时间复杂度

对于n×n的方阵，时间复杂度为O(n³)，适用于中小规模矩阵。

优化方案（针对稀疏矩阵） #

如果矩阵中1的数量远小于总元素数，可以通过预存每列的1的行号，用双指针法快速计算列对的共同行数量，减少无效检查。

步骤

1. 预处理：为每一列存储所有值为1的行号（按行号升序排列）。
2. 遍历所有列对，用双指针法找出两个列的行号列表的交集大小k。
3. 累加C(k,2)到总数中。

Python代码示例

def count_rectangles_optimized(matrix):
    if not matrix or not matrix[0]:
        return 0
    row_count = len(matrix)
    col_count = len(matrix[0])
    
    # 预存每一列中值为1的行号
    col_ones = [[] for _ in range(col_count)]
    for r in range(row_count):
        for c in range(col_count):
            if matrix[r][c] == 1:
                col_ones[c].append(r)
    
    total = 0
    # 遍历所有列对
    for c1 in range(col_count):
        list1 = col_ones[c1]
        for c2 in range(c1 + 1, col_count):
            list2 = col_ones[c2]
            # 双指针求交集大小
            i = j = common_count = 0
            while i < len(list1) and j < len(list2):
                if list1[i] == list2[j]:
                    common_count += 1
                    i += 1
                    j += 1
                elif list1[i] < list2[j]:
                    i += 1
                else:
                    j += 1
            total += common_count * (common_count - 1) // 2
    return total

# 测试示例矩阵
print(count_rectangles_optimized(test_matrix))  # 输出：8

时间复杂度

取决于矩阵的稀疏程度，最坏情况仍为O(n³)，但稀疏场景下远快于基础方案。

内容的提问来源于stack exchange，提问作者user43283