文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：有效的数独

出处：36. 有效的数独

难度

2 级

题目描述

要求

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

1. 每一行必须包含数字 1-9\texttt{1-9}1-9 且没有重复。
2. 每一行必须包含数字 1-9\texttt{1-9}1-9 且没有重复。
3. 每一个九宫格必须包含数字 1-9\texttt{1-9}1-9 且没有重复。

注意：

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

示例

示例 1：

输入：board=\texttt{board = }board = 
[["5","3",".",".","7",".",".",".","."]\texttt{[["5","3",".",".","7",".",".",".","."]}[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]\texttt{,["6",".",".","1","9","5",".",".","."]},["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]\texttt{,[".","9","8",".",".",".",".","6","."]},[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]\texttt{,["8",".",".",".","6",".",".",".","3"]},["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]\texttt{,["4",".",".","8",".","3",".",".","1"]},["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]\texttt{,["7",".",".",".","2",".",".",".","6"]},["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]\texttt{,[".","6",".",".",".",".","2","8","."]},[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]\texttt{,[".",".",".","4","1","9",".",".","5"]},[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]\texttt{,[".",".",".",".","8",".",".","7","9"]]},[".",".",".",".","8",".",".","7","9"]]
输出：true\texttt{true}true

示例 2：

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

数据范围

• board.length=9\texttt{board.length} = \texttt{9}board.length=9
• board[i].length=9\texttt{board[i].length} = \texttt{9}board[i].length=9
• board[i][j]\texttt{board[i][j]}board[i][j] 是一位数字 1-9\texttt{1-9}1-9 或者 ‘.’\texttt{`.'}‘.’

解法

思路和算法

这道题要求判断一个已经填入部分数字的数独是否有效，不需要考虑数独是否有解，只需要考虑每一行、每一列和每一个九宫格中的数字是否都是唯一的。以下将一行、一列和一个九宫格统称为「判断单位」。

为了判断数独是否有效，需要记录每一个判断单位中的每个数字的出现情况。数独中的每一个单元格都对应一行、一列和一个九宫格，遍历数组一次即可判断数独是否有效。

对于数独的第 iii 行第 jjj 列的单元格，其中 0≤i,j<90 \le i, j < 90≤i,j<9，其所在的行下标和列下标分别为 iii 和 jjj，其所在的九宫格的行编号和列编号分别为 ⌊i3⌋\Big\lfloor \dfrac{i}{3} \Big\rfloor⌊3i​⌋ 和 ⌊j3⌋\Big\lfloor \dfrac{j}{3} \Big\rfloor⌊3j​⌋，由于行编号和列编号都小于 333，因此可以将行编号和列编号转换为九宫格的编号：⌊i3⌋×3+⌊j3⌋\Big\lfloor \dfrac{i}{3} \Big\rfloor \times 3 + \Big\lfloor \dfrac{j}{3} \Big\rfloor⌊3i​⌋×3+⌊3j​⌋。

有效的数独要求每一个判断单位中每一个数字都只能出现一次，因此可以使用哈希表记录每个数字的出现次数，如果出现次数大于一次则是无效的数独。其实，并不需要记录每个数字的出现次数，只需要记录每个数字是否出现过即可。记录每个数字是否出现过的做法如下。

对于遍历到的每个单元格，如果尚未填入数字则跳过，如果已经填入数字则执行以下操作：

1. 判断该单元格所在的三个判断单位中该数字是否已经出现过，如果至少一个判断单位中该数字已经出现过，则和当前遍历到的单元格重复，因此是无效的数独，返回 false\text{false}false；

2. 如果三个判断单位中该数字都没有出现过，则将三个判断单位中该数字的状态都更新为已经出现过。

如果遍历结束之后没有出现同一个判断单位中有重复数字的情况，则是有效的数独，返回 true\text{true}true。

实现方面有两点技巧：

1. 由于数独中的数字范围有限且是连续的正整数，因此可以使用数组代替哈希表；

2. 对于每个判断单位，可以将代替哈希表的数组长度设为 101010，其目的是将下标范围设为 000 到 999，使得下标可以直接和数字对应，不需要进行下标转换。

代码

class Solution {public boolean isValidSudoku(char[][] board) {boolean[][] rows = new boolean[9][10];boolean[][] columns = new boolean[9][10];boolean[][] subboxes = new boolean[9][10];for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {char c = board[i][j];if (c == '.') {continue;}int subboxRowIndex = i / 3, subboxColumnIndex = j / 3;int subboxIndex = subboxRowIndex * 3 + subboxColumnIndex;int digit = c - '0';if (rows[i][digit] || columns[j][digit] || subboxes[subboxIndex][digit]) {return false;}rows[i][digit] = true;columns[j][digit] = true;subboxes[subboxIndex][digit] = true;}}return true;}
}

复杂度分析

• 时间复杂度：O(1)O(1)O(1)。数独的大小固定，有 818181 个单元格，对每个单元格遍历一次。

• 空间复杂度：O(1)O(1)O(1)。空间复杂度主要取决于记录每一行、每一列和每一个九宫格中出现的数字的哈希表，由于数独的大小固定，因此哈希表的空间也是固定的。