分析

• 本题的考点：哈希表。

• 开辟一个哈希表依次判断行、列、九宫格是否满足条件即可，注意这里枚举的是九宫格的左上角坐标。此方法使用c++实现。

• 或者可以开辟三个哈希表，对行、列、九宫格一起判断，这里九宫格从左向右，从上向下标号依次是0~8，对于某个坐标(i, j)，其所在的九宫格编号为i/3 * 3 + j/3。此方法采用Java实现。

代码

• C++

class Solution {
public:
    bool isValidSudoku(vector<vector<char>> &board) {

        bool st[9];

        // 判断行
        for (int i = 0; i < 9; i++) {
            memset(st, 0, sizeof(st));
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    if (st[t]) return false;
                    st[t] = true;
                }
            }
        }

        // 判断列
        for (int i = 0; i < 9; i++) {
            memset(st, 0, sizeof(st));
            for (int j = 0; j < 9; ++j) {
                if (board[j][i] != '.') {
                    int t = board[j][i] - '1';
                    if (st[t]) return false;
                    st[t] = true;
                }
            }
        }

        // 判断小方格
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                memset(st, 0, sizeof(st));
                for (int x = 0; x < 3; ++x) {
                    for (int y = 0; y < 3; ++y) {
                        if (board[i + x][j + y] != '.') {
                            int t = board[i + x][j + y] - '1';
                            if (st[t]) return false;
                            st[t] = true;
                        }
                    }
                }
            }
        }

        return true;
    }
};

• Java

class Solution {
    public boolean isValidSudoku(char[][] board) {

        boolean[][] row = new boolean[9][10];
        boolean[][] col = new boolean[9][10];
        boolean[][] box = new boolean[9][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;

                int t = board[i][j] - '0';
                int index = i / 3 * 3 + j / 3;
                if (row[i][t] || col[j][t] || box[index][t]) return false;

                row[i][t] = true;  // (i, j)在第i行
                col[j][t] = true;  // (i, j)在第j列
                box[index][t] = true;  // (i, j)在第index个九宫格
            }
        }
        return true;
    }
}

时空复杂度分析

• 时间复杂度：$O(1)$。遍历的次数是固定的。

• 空间复杂度：$O(1)$。