题目描述（中等难度）

一个 9 * 9 的数独的棋盘。判断已经写入数字的棋盘是不是合法。需要满足下边三点，

• 每一行的数字不能重复

• 每一列的数字不能重复

只能是 1 - 9 中的数字，不需要考虑数独最后能不能填满。

解法一 暴力解法

需要满足三条，那就一条一条判断。

空间复杂度：O（1）。

解法二

参考，上边的算法遍历了三遍，我们能不能只遍历一遍。

我们可以这样想一下，如果有一副纸牌，怎么看它有没有重复的？

第一种我们可以像之前一样，第一遍先看红桃，再看黑桃，再看方片，再看梅花，这样就看了四遍。我们其实可以每拿到一张牌，就把它放在一个位置，我们把一类放在同一位置。红桃放在一起，黑桃放在一起……放的过程中如果有重复的就可以结束了。

在这里的话，我们就可以把第一行的放在一起，第二行的放在一起……第一列的放在一起，第二列的放在一起……第一个小棋盘的放在一起，第二个小棋盘的放在一起……

我们用 HashSet 实现放在一起的作用，但是这样的话总共就是 9 行，9 列，9 个小棋盘，27 个 HashSet 了。我们其实可以在放的时候标志一下，例如

• 如果第 4 行有一个数字 8，我们就 (8)4，把 “(8)4”放进去。
• 如果第 5 行有一个数字 6，我们就 5(6)，把 “5(6)”放进去。

时间复杂度：如果棋盘大小总共是 n，那么只遍历了一次，就是 O（n）。

空间复杂度：如果棋盘大小总共是 n，最坏的情况就是每个地方都有数字，就需要存三次，O（n）。

其实，想到了标识，其实我们可以标识的更彻底些，直接写出来。

总

第二种解法的作者太太聪明了！自己规定格式这种思想，很棒。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情