Java C++ 算法题解leetcode1582二进制矩阵特殊位置

题目说明

在二进制矩阵中寻找特殊位置。特殊位置的定义是该位置的行和列的所有元素都是 0。

给出一个N*N 的二进制矩阵，你需要找到特殊的位置。以整数数组的形式返回特殊位置的行和列，如果不存储，返回 [-1, -1]。

解题思路

首先，遍历整个矩阵，找到所有行和列元素都为 0 的位置，将其存放到 set 集合中。

最后，对行和列分别进行遍历，判断当前行和当前列是否为 set 集合中的元素，如果是，则返回该行和该列。

代码实现

class Solution {
    public int[] findSpecialInteger(int[][] matrix) {
        Set<Integer> set = new HashSet<>(); // 用于存放特殊位置的 set 集合
        int n = matrix.length;

        // 遍历整个矩阵，找到所有行和列元素都为 0 的位置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    boolean rowFlag = true; // 标记该行是否全部为 0
                    boolean colFlag = true; // 标记该列是否全部为 0

                    // 判断该行是否全部为 0
                    for (int k = 0; k < n; k++) {
                        if (matrix[i][k] != 0) {
                            rowFlag = false;
                            break;
                        }
                    }

                    // 判断该列是否全部为 0
                    for (int k = 0; k < n; k++) {
                        if (matrix[k][j] != 0) {
                            colFlag = false;
                            break;
                        }
                    }

                    // 如果该行和该列全部都为 0，则将其加入 set 集合中
                    if (rowFlag && colFlag) {
                        set.add(i * n + j);
                    }
                }
            }
        }

        // 对行和列分别进行遍历，判断当前行和当前列是否为 set 集合中的元素，如果是，则返回该行和该列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (set.contains(i * n + j)) {
                    return new int[]{i, j};
                }
            }
        }

        return new int[]{-1, -1}; // 如果不存在特殊位置，则返回 [-1, -1]
    }
}

示例说明

示例 1

输入:

matrix = [[1,0,0],
          [0,0,1],
          [1,1,0]]

输出:

[1, 1]

解释:
该矩阵中，位置 (1, 1) 的行和列均为 0，因此它是一个特殊位置，返回 [1, 1]。

示例 2

输入:

matrix = [[1,0,0,1],
          [0,1,1,0],
          [0,1,1,0],
          [1,0,0,1]]

输出:

[-1, -1]

解释:
该矩阵中，不存在特殊位置，返回 [-1, -1]。