36、有效的数独【中等】

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

• 示例1：
  
  输入：board =
  [["5","3",".",".","7",".",".",".","."]
  ,["6",".",".","1","9","5",".",".","."]
  ,[".","9","8",".",".",".",".","6","."]
  ,["8",".",".",".","6",".",".",".","3"]
  ,["4",".",".","8",".","3",".",".","1"]
  ,["7",".",".",".","2",".",".",".","6"]
  ,[".","6",".",".",".",".","2","8","."]
  ,[".",".",".","4","1","9",".",".","5"]
  ,[".",".",".",".","8",".",".","7","9"]]
  输出：true

• 示例 2：
  输入：board =
  [["8","3",".",".","7",".",".",".","."]
  ,["6",".",".","1","9","5",".",".","."]
  ,[".","9","8",".",".",".",".","6","."]
  ,["8",".",".",".","6",".",".",".","3"]
  ,["4",".",".","8",".","3",".",".","1"]
  ,["7",".",".",".","2",".",".",".","6"]
  ,[".","6",".",".",".",".","2","8","."]
  ,[".",".",".","4","1","9",".",".","5"]
  ,[".",".",".",".","8",".",".","7","9"]]
  输出：false
  解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

• 提示：
  board.length == 9
  board[i].length == 9
  board[i][j] 是一位数字（1-9）或者 '.'

方法一：依次遍历

1.1 思路分析

有效的数独满足以下三个条件：

1. 同一个数字在每一行只能出现一次；
2. 同一个数字在每一列只能出现一次；
3. 同一个数字在每一个小九宫格只能出现一次。

可以依次遍历，统计每行、每列、每子块是否满足条件。可以用哈希表，由于是1-9的数字，所以也可以用数组来记录出现的次数，下标代表数字，所存元素代表出现次数。这里比较难的是子块如何记录，同行列一样也可以用数组，但是需要三维数组，因为子块是3*3的，所以第三个索引便代表数字。
rows[i][index]代表每行各个数字出现的次数；
columns[j][index]代表每列各个数字出现的次数；
比较难想到的是子块的表示
subboxes[i/3][j/3][index]代码每个子块各个数字出现的次数。

1.2 代码实现

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];           // 行
        int[][] columns = new int[9][9];        // 列
        int[][][] subboxes = new int[3][3][9];   // 9个子块
        for (int i=0; i<9; i++){
            for (int j=0; j<9; j++){
                char c = board[i][j];   // 获取元素
                if (c-'.' != 0){
                    // 如果c不为'.'
                    int index = c - '0' - 1; // -1是因为数组下标是从0开始的
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i/3][j/3][index]++;
                    // 如果其中一个大于1
                    if(rows[i][index]>1 || columns[j][index]>1 || subboxes[i/3][j/3][index]>1){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

1.3 测试结果

1.4 复杂度

• 时间复杂度：O(1)。始终是9*9
• 空间复杂度：O(1)。始终是9*9