[算法]判断二维数组中是否存在冲突&&有效的数独

题目

给定一个8x8二维数组，请判断数组中是否存在冲突，冲突的定义：同一行或同一列中存在1个以上的1。

例如：以下数组不冲突

[[1,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0]
[0,0,1,0,0,0,0,0]
[0,0,0,1,0,0,0,0]
[0,0,0,0,1,0,0,0]
[0,0,0,0,0,1,0,0]
[0,0,0,0,0,0,1,0]
[0,0,0,0,0,0,0,1]]

以下数组则存在冲突(实际上只是把第4行最后一个改成1)

[[1,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0]
[0,0,1,0,0,0,0,0]
[0,0,0,1,0,0,0,1]
[0,0,0,0,1,0,0,0]
[0,0,0,0,0,1,0,0]
[0,0,0,0,0,0,1,0]
[0,0,0,0,0,0,0,1]]

题解

比较容易想到的就是遍历元素，如果是1就去拿同行同列来判断是否存在重复的1，可行，问题在于效率极低（取同列的需要再次遍历）。换个角度想，先初始化行/数组，来跟踪元素所在行列的元素，遇到1时判断所在行列数组里是否有重复即可。

function isConflict(board) {
    const row = [],col = []
    for(let i = 0; i<8; i++){
        row[i] = new Set()
        col[i] = new Set()
    }
    for(let i = 0; i<8; i++){
        for(let j = 0; j<8; j++){
            if(board[i][j] === 0) continue; // 略过0
            // 遍历到第i行第j列的数,判断这个数在其所在的行/列有没有出现过
            if(row[i].has(board[i][j]) || col[j].has(board[i][j])){
                return true;
            }
            // 将元素加入对应的行列以跟踪
            row[i].add(board[i][j])
            col[j].add(board[i][j])
        }
    }
    return false;
};

其实只存在两个元素的话，压根不需要一个数组或者哈希Set来存，直接标记为true即可，可以节省不少空间，也不用初始化了，如下：

function isConflict(board) {
    const row = [],col = []
    for(let i = 0; i<8; i++){
        for(let j = 0; j<8; j++){
            if(board[i][j] === 0) continue; // 略过0
            // 遍历到第i行第j列的数,判断这个数在其所在的行/列是否存在标记
            if(row[i] || col[j]){
                return true;
            }
            // 标记行列
            row[i] = col[j] = true
        }
    }
    return false;
};

更进一步

来看一道leetcode题，36. 有效的数独。题目不赘述，判断行/列/九宫格内是否存在重复数据即可，稍微难的在于如何判断是否在同一九宫格。九宫格box可以理解为更大范围的行列(3*3), 所以元素对应坐标除以3即可获得所在的box：

box_index = (row / 3) * 3 + columns / 3，其中 / 是整数除法

更多的理解可以参考官方题解，里边有图来辅助理解。

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
        const row = [],col = [], box = []
        for(let i = 0; i<9; i++){
            // 这里也可以换成Set
            row[i] = []
            col[i] = []
            box[i] = []
        }
        for(let i = 0; i<9; i++){
            for(let j = 0; j<9; j++){
                // 遍历到第i行第j列的那个数,我们要判断这个数在其所在的行有没有出现过，
                // 同时判断这个数在其所在的列有没有出现过
                // 同时判断这个数在其所在的box中有没有出现过
                if(board[i][j] == '.') continue;
                const box_index = Math.floor(j/3) + Math.floor(i/3)*3 // 九宫格
                const curNumber = Number(board[i][j]);
                if(row[i][curNumber] || col[j][curNumber] || box[box_index][curNumber]){
                    return false;
                } 
                row[i][curNumber] = col[j][curNumber] = box[box_index][curNumber] = 1;
            }
        }
        return true;
};

以上的空间复杂度同样存在优化空间。

注意这里只用判断是否存在重复，并不关注数独是否有解。有解数独的生成一般有随机法、挖洞法，后者效率更高。关于数独，leetcode也有一道解数独，可以尝试做一下。

metroluffy / blog

[算法]判断二维数组中是否存在冲突&&有效的数独 #33

题目

题解

更进一步

参考