跳到主要内容

操作

题一、矩阵​

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。

示例1:

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例2:

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

方案A、广度优先遍历​

function updateMatrix(matrix){
    let direction=[[-1,0],[1,0],[0,-1],[0,1]];
    let m=matrix.length;
    let n=matrix[0].length;
    let dist=new Array(m).fill(0).map(val=>new Array(n).fill(0));
    let seen=new Array(m).fill(false).map(val=>new Array(n).fill(false));
    let queue=[];
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(matrix[i][j]==0){
                queue.push([i,j]);
                seen[i][j]=true;
            }
        }
    }
    while(queue.length){
        let cell=queue.shift();
        let i=cell[0];
        let j=cell[1];
        for(let d=0;d<4;d++){
            let ni=i+direction[d][0];
            let nj=j+direction[d][1];
            if(ni>=0&&ni<m&&nj>=0&&nj<n&&!seen[ni][nj]){
                dist[ni][nj]=dist[i][j]+1;
                queue.push([ni,nj]);
                seen[ni][nj]=true;
            }
        }
    }
    return dist;
}

性能分析:

  • 时间复杂度：O(rc)，其中 r 为矩阵行数，c 为矩阵列数，即矩阵元素个数。广度优先搜索中每个位置最多只会被加入队列一次，因此只需要 O(rc) 的时间复杂度。
  • 空间复杂度：O(rc)，其中 r 为矩阵行数，c 为矩阵列数，即矩阵元素个数。除答案数组外，最坏情况下矩阵里所有元素都为 0，全部被加入队列中，此时需要 O(rc) 的空间复杂度。

方案B、动态规划​

function updateMatrix(matrix){
    let m=matrix.length;
    let n=matrix[0].length;
    let dist=new Array(m).fill(0).map(val=>new Array(n).fill(Infinity));
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(matrix[i][j]==0){
                dist[i][j]=0;
            }
        }
    }
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(i-1>=0){
                dist[i][j]=Math.min(dist[i][j],dist[i-1][j]+1);
            }
            if(j-1>=0){
                dist[i][j]=Math.min(dist[i][j],dist[i][j-1]+1);
            }
        }
    }
    for(let i=m-1;i>=0;i--){
        for(let j=n-1;j>=0;j--){
            if(i+1<m){
                dist[i][j]=Math.min(dist[i][j],dist[i+1][j]+1);
            }
            if(j+1<n){
                dist[i][j]=Math.min(dist[i][j],dist[i][j+1]+1);
            }
        }
    }
    return dist;
}

性能分析:

题二、矩阵置零​

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

进阶：

  • 一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

示例1:

输入：
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出：
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例2:

输入：
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出：
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

方案A、使用标记数组​

  • 借助两个标记数组分别记录每一行和每一列是否有零出现
    • rowArray : 记录行是否出现 零
    • colArray : 记录列是否出现 零
  • 通过标记数组更新原数组即可
function createMatrix(array,row,col){
    let matrix=[];
    for(let i=0;i<row;i++){
        matrix[i]=[];
        for(let j=0;j<col;j++){
            matrix[i][j]=array.shift();
        }
    }
    return matrix
}
function setZero(matrix){
    let row=matrix.length;
    let col=matrix[0].length;
    let rowArr=new Array().fill(false);
    let colArr=new Array().fill(false);;
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            if(matrix[i][j]==0){
                rowArr[i]=colArr[j]=true;
            }
        }
    }
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            if(rowArr[i]||colArr[j]){
                matrix[i][j]=0;
            }
        }
    }
}
// let matrix=createMatrix([1,2,3,4,0,6,7,8,9],3,3);
let matrix=createMatrix([0,1,2,0,3,4,5,2,1,3,1,5],3,4);
setZero(matrix)
console.log(matrix);

性能分析:

时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。

空间复杂度：O(m+n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。

方案B、使用两个标记变量​

  • 遍历第一行和第一列是否有 0 出现（标记变量标记了第一行和第一列，后续遍历要排除第一行和第一列，防止后续更新覆盖）

    • rowFlag: 如果第一行有 零 出现置为 true

    • colFlag: 如果第一列有 零 出现置为 true

  • 将第一行和第一列作为标记数组

    • matrix[0][i] : 记录除第一列以外的哪一列出现了 0
    • matrix[i][0] : 记录除第一行以外的哪一行出现了 0

  • 通过标记数组更新 matrix

  • 通过 rowFlag 和 colFlag 更新第一行和第一列

function createMatrix(array,row,col){
    let matrix=[];
    for(let i=0;i<row;i++){
        matrix[i]=[];
        for(let j=0;j<col;j++){
            matrix[i][j]=array.shift();
        }
    }
    return matrix
}
function setZero(matrix){
    let row=matrix.length;
    let col=matrix[0].length;
    let rowFlag=false;
    let colFlag=false;
    for(let i=0;i<row;i++){
        if(matrix[i][0]==0){
            colFlag=true;
            break
        }
    }
    for(let i=0;i<col;i++){
        if(matrix[0][i]==0){
            rowFlag=true;
            break
        }
    }
    for(let i=1;i<row;i++){
        for(let j=1;j<col;j++){
            if(matrix[i][j]==0){
                matrix[i][0]=matrix[0][j]=0;
            }
        }
    }
    for(let i=1;i<row;i++){
        for(let j=1;j<col;j++){
            if(matrix[i][0]==0||matrix[0][j]==0){
                matrix[i][j]=0;
            }
        }
    }
    if(rowFlag){
        for(let i=0;i<col;i++){
            matrix[0][i]=0;
        }
    }
    if(colFlag){
        for(let i=0;i<row;i++){
            matrix[i][0]=0;
        }
    }
}
// let matrix=createMatrix([1,2,3,4,0,6,7,8,9],3,3);
let matrix=createMatrix([0,1,2,0,3,4,5,2,1,3,1,5],3,4);
setZero(matrix)
console.log(matrix);

性能分析:

  • 时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。

  • 空间复杂度：O(1)。我们只需要常数空间存储若干变量。

方案C、使用一个标记变量​

  • 定义一个标记变量，查看第一列是否有 0 出现(标记变量标记了第一列，后续遍历要排除第一列，防止后续更新覆盖)
  • 将第一行和第一列作为标记数组
    • matrix[0][i] : 记录除第一列以外的哪一列出现了 0
    • matrix[i][0] : 记录哪一行出现了 0
  • 通过标记数组更新 matrix （更新时要从最后一行开始，防止更新时覆盖掉第一行的标记）
  • 通过 colFlag 更新第一列
function createMatrix(array,row,col){
    let matrix=[];
    for(let i=0;i<row;i++){
        matrix[i]=[];
        for(let j=0;j<col;j++){
            matrix[i][j]=array.shift();
        }
    }
    return matrix
}
function setZero(matrix){
    let row=matrix.length;
    let col=matrix[0].length;
    let colFlag=false;
    for(let i=0;i<row;i++){
        if(matrix[i][0]==0){
            colFlag=true;
        }
        for(let j=1;j<col;j++){
            if(matrix[i][j]==0){
                matrix[0][j]=matrix[i][0]=0;
            }
        }
    }
    for(let i=row-1;i>=0;i--){
        for(let j=1;j<col;j++){
            if(matrix[0][j]==0||matrix[i][0]==0){
                matrix[i][j]=0;
            }
        }
        if(colFlag){
            matrix[i][0]=0;
        }
    }
}
// let matrix=createMatrix([1,2,3,4,0,6,7,8,9],3,3);
let matrix=createMatrix([0,1,2,0,3,4,5,2,1,3,1,5],3,4);
setZero(matrix)
console.log(matrix);

性能分析:

  • 时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。

  • 空间复杂度：O(1)。我们只需要常数空间存储若干变量。

题三、对角线遍历​

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

示例:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

输出:  [1,2,4,7,5,3,6,8,9]

方案A、对角线迭代和翻转​

思路:

  • 将第一行和最后一列的每一个元素作为起点，遍历每一个元素

    • 起点范围 0 < i < row+col-1

    • 起点变化规律:

      • row：i<col?0:i-col+1

      • col: i<col?i:col-1

  • 当此时的对角线为偶数时，要翻转遍历的结果

  • 将遍历的结果放到 result 中

function createMatrix(array,row,col){
    let matrix=[];
    for(let i=0;i<row;i++){
        matrix[i]=[];
        for(let j=0;j<col;j++){
            matrix[i][j]=array.shift();
        }
    }
    return matrix
}
function diagonalTraversal(matrix){
    let row=matrix.length;
    let col=matrix[0].length;
    let result=[];
    for(let i=0;i<row+col-1;i++){
        let rowStart=i<col?0:i-col+1;
        let colStart=i<col?i:col-1;
        let temp=[];
        while(rowStart<row&&colStart>=0){
        temp.push(matrix[rowStart++][colStart--]);
        }
        if(i%2==0){
        temp=temp.reverse();
        }
        for(let j=0;j<temp.length;j++){
        result.push(temp[j]);
        }
    }
    return result
}
let matrix=createMatrix([1,2,3,4,5,6,7,8,9],3,3);
console.log(diagonalTraversal(matrix));

性能分析:

时间复杂度：O(N⋅M)，数组有 N 行 M 列。对于所有奇数对角线上的元素，需要两次处理，迭代和翻转。为了节省空间，需要遍历新对角线之前清除中间使用的空间，该操作需要 O(K) 的复杂度度，其中 K 是数组长度。因此至少处理两次数组中的元素，渐进复杂度为 O(N⋅M)。

空间复杂度：O(min(N,M))，额外空间用于存储每条对角线的中间数组，该数组长度为 N 和 M 的最小值。注意：对角线延伸到索引超出范围结束。

方案B、模拟​

思路:

  • 初始化起始点和遍历方向

    • rowStart、colStart 为当前起始点，初始从 [0][0] 开始

    • direction 为当前遍历方向，初始从上遍历

  • 从每一个起始点开始遍历，将遍历到的元素存到 result 中

    • 将元素存到 result 中

    • 向后移动行和列，通过中间变量保存

      • 行的变化 direction==1? 行-1:行+1

      • 列的变化 direction==1? 列+1:列-1

    • 判断当前遍历是否越界，如果越界更改起始点和遍历方向

      • 越界条件: 行<0||行==row||列<0||列==col

      • 更改起始点

        • 如果 direction==1 起始点的变化

        • 如果 direction==0 起始点的变化

      • 更改遍历方向 direction=1-direction

    • 如果没有越界，将行的变化和列的变化赋给起始点

function createMatrix(array,row,col){
    let matrix=[];
    for(let i=0;i<row;i++){
        matrix[i]=[];
        for(let j=0;j<col;j++){
            matrix[i][j]=array.shift();
        }
    }
    return matrix
}
function diagonalTraversal(matrix){
    let row=matrix.length;
    let col=matrix[0].length;
    let rowStart=0;
    let colStart=0;
    let direction=1;
    let result=[];
    while(rowStart<row&&colStart<col){
        result.push(matrix[rowStart][colStart]);
        let rowTemp=direction==1?rowStart-1:rowStart+1;
        let colTemp=direction==1?colStart+1:colStart-1;
        if(rowTemp<0||rowTemp==row||colTemp<0||colTemp==col){
        if(direction==1){
            rowStart+=(colStart==col-1)?1:0;
            colStart+=(colStart<col-1)?1:0;
        }else{
            colStart+=(rowStart==row-1)?1:0;
            rowStart+=(rowStart<row-1)?1:0;
        }
        direction=1-direction;
        }else{
        rowStart=rowTemp;
        colStart=colTemp;
        }
    }
    return result
}
let matrix=createMatrix([1,2,3,4,5,6,7,8,9],3,3);
console.log(diagonalTraversal(matrix));

性能分析:

时间复杂度：O(N⋅M)，每个元素只处理一次。

空间复杂度：O(1)，不使用额外空间。注意：输出数组空间不计入空间复杂度，因为这是题目要求的空间。空间复杂度应该指除了最终数组以外的空间。上一个方法中是中间数组，该方法中只有几个变量。

题四、最大子矩阵​

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

示例:

输入：
[
   [-1,0],
   [0,-1]
]
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵

方案A、前缀和​

思路:

  • 枚举每个矩形的上下边界，计算对应列的和，问题转换为一维问题: 在一维数组中求出连续的子数组最大和
  • 存储每个矩形的起始地址和结尾地址: point[0]=i;point[1]=temp; point[2]=j;point[3]=c;
function getMaxMatrix(matrix) {
    let row=matrix.length;
    let col=matrix[0].length;
    let result=-Infinity;
    let point=new Array(4);
    for(let i=0;i<row;i++){
        let sum=new Array(col).fill(0);
        for(let j=i;j<row;j++){
            let res=0;
            let temp=0;
            for(let k=0;k<col;k++){
                sum[k]+=matrix[j][k];
                res+=sum[k];
                if(res<sum[k]){
                    res=sum[k];
                    temp=k;
                }
                if(res>result){
                    point[0]=i;
                    point[1]=temp;
                    point[2]=j;
                    point[3]=k;
                    result=res;
                }
            }
        }
    }
    return point;
};

性能分析:

题五、元素和为目标值的子矩阵数量​

给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。

如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。

示例1:

输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。

示例2:

输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。

方案A、前缀和与哈希表​

思路: 该问题可以转化为一维问题给定一个整数数组和一个整数target,计算该数组中子数组和等于target的子数组个数

  • 对于每列的元素和sum的计算，在枚举子矩阵上边界i时，初始下边界j为i,此时sum就是距离第i行的元素。每次向下延长下边界j时，可以将矩阵第j行的元素累加到sum中。
function subarraySum(nums,k){
    const map=new Map();
    map.set(0,1);
    let count=0;
    let prev=0;
    for(let item of nums){
        prev+=item;
        if(map.has(prev-k)){
            count+=map.get(prev-k);
        }
        map.set(prev,(map.get(prev)||0)+1);
    }
    return count;
}
function numSubmatrixSumTarget(matrix, target) {
    let result=0;
    const row=matrix.length;
    const col=matrix[0].length;
    for(let i=0;i<row;i++){
        let sum=new Array(col).fill(0);
        for(let j=i;j<row;j++){
            for(let l=0;l<col;l++){
                sum[l]+=matrix[j][l];
            }
            result+=subarraySum(sum,target);
        } 
    }
    return result;
};

性能分析:

  • 时间复杂度: O(m^2*n)
  • 空间复杂度: O(n)

题六、二维数组中的查找​

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

方案A、线性查找​

思路: 由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。

  1. 若数组为空，返回 false

  2. 初始化行下标为 0，列下标为二维数组的列数减 1

  3. 重复下列步骤，直到行下标或列下标超出边界

    • 获得当前下标位置的元素 num
    • 如果 num 和 target 相等，返回 true
    • 如果 num 大于 target，列下标减 1
    • 如果 num 小于 target，行下标加 1

循环体执行完毕仍未找到元素等于 target ，说明不存在这样的元素，返回 false

实现

function findNumberIn2DArray(matrix, target) {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    return false;
  }
  let rows = matrix.length;
  let columns = matrix[0].length;
  let row = 0;
  let column = columns - 1;
  while (row < rows && column >= 0) {
    let num = matrix[row][column];
    if (num === target) {
      return true;
    } else if (num > target) {
      column--;
    } else {
      row++;
    }
  }
  return false;
}