草庐IT

LeetCode - #73 矩阵置零

Swift社区 2023-09-15 原文

前言

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新了 72 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

1. 描述

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

2. 示例

示例 1

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

示例 2

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

约束条件：

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1`

3. 答案

class SetMatrixZeroes {
    func setZeroes(_ matrix: inout [[Int]]) {
        var rowHasZero = false, colHasZero = false
        let m = matrix.count, n = matrix[0].count
  
        for i in 0..<m where matrix[i][0] == 0 {
            colHasZero = true
            break
        }
  
        for i in 0..<n where matrix[0][i] == 0 {
            rowHasZero = true
            break
        }
  
        for i in 1..<m {
            for j in 1..<n {
                if matrix[i][j] == 0 {
                    matrix[0][j] = 0
                    matrix[i][0] = 0
                }
            }
        }
  
        for i in 1..<m {
            for j in 1..<n {
                if matrix[0][j] == 0 || matrix[i][0] == 0 {
                    matrix[i][j] = 0
                }
            }
        }
  
        if rowHasZero {
            for i in 0..<n {
                matrix[0][i] = 0
            }
        }
  
        if colHasZero {
            for i in 0..<m {
                matrix[i][0] = 0
            }
        }
    }
}
  • 主要思想：使用第一行和 col 来跟踪行和 col 是否应该设置为 0，记住它们应该与矩阵的其他部分分开。
  • 时间复杂度： O(n^2)
  • 空间复杂度： O(1)

该算法题解的仓库：LeetCode-Swift

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。

后续还会翻译大量资料到我们公众号，有感兴趣的朋友，可以加入我们。

LeetCode73matrixstrongcode

有关LeetCode - #73 矩阵置零的更多相关文章

  1. 旋转矩阵的几何意义 - 2

    点向量坐标矩阵的几何意义介绍旋转矩阵的几何含义之前，先介绍一下点向量坐标矩阵的几何含义点：在一维空间下就是一个标量，如同一条直线上，以任意某一个位置为0点，以一定的尺度间隔为1，2，3...,相反方向为-1，-2，-3...；如此就形成了一维坐标系，这时候任何一个点都可以用一个数值表示，如点p1=5，即即从原点出发沿着x轴正方向移动5个尺度；点p2=-3，负方向移动3个尺度；     在一维坐标系上过原点做垂直于一维坐标系的直线，则形成了二维坐标系，此时描述一个点需要两个数值来表示点p3=（3，2），即从原点出发沿着x轴正方向移动3个尺度，在此基础上沿着y轴正方向移动两个尺度的位置就是点p3。

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. 华为OD机试真题 C++ 实现【带传送阵的矩阵游离】【2023 Q2 | 200分】 - 2

            所有题目均有五种语言实现。C实现目录、C++实现目录、Python实现目录、Java实现目录、JavaScript实现目录题目n行m列的矩阵，每个位置上有一个元素你可以上下左右行走，代价是前后两个位置元素值差的绝对值.另外，你最多可以使用一次传送阵(只能从一个数跳到另外一个相同的数)求从走上角走到右下角最少需要多少时间。输入描述：第一行两个整数n,m，分别代表矩阵的行和列。后面n行，每行m个整数，分别代表矩阵中的元素。输出描述：一个整数，表示最少需要多少时间。

  4. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  5. 欧拉角表示的姿态矩阵（313和312转序） - 2

    一、习惯约定图片来自PSINS（高精度捷联惯导算法）PSINS工具箱入门与详解.pptx二、基本旋转矩阵绕x轴逆时钟旋转α\alphaα角度Rx(α)=[ 1000cos⁡αsin⁡α0−sin⁡αcos⁡α]R_x(\alpha)=\begin{bmatrix}\1&0&0\\0&\cos\alpha&\sin\alpha\\0&-\sin\alpha&\cos\alpha\end{bmatrix}Rx​(α)=​ 100​0cosα−sinα​0sinαcosα​​绕y轴逆时钟旋转α\alphaα角度Ry(α)=[ cos⁡α0−sin⁡α010sin⁡α0cos⁡α]R_y(\alpha

  6. 欧拉角、旋转矩阵及四元数 - 2

    欧拉角、旋转矩阵及四元数1.简介2.欧拉角2.1欧拉角定义2.2右手系和左手系2.3转换流程3.旋转矩阵4.四元数4.1四元数与欧拉角和旋转矩阵之间等效变换4.2测试Matlab代码5.总结1.简介常用姿态参数表达方式包括方向余弦矩阵、欧拉轴/角参数、欧拉角、四元数以及罗德里格参数等。高分辨率光学遥感卫星主要采用欧拉角与四元数对姿态参数进行描述。这里着重讲解欧拉角、旋转矩阵和四元数。2.欧拉角2.1欧拉角定义欧拉角是表征刚体旋转的一种方法之一，由莱昂哈德·欧拉引入的三个角度，用于描述刚体相对于固定坐标系的方向。在摄影测量、空间科学或其它技术领域，一般用一组（三个）欧拉角描述两个空间坐标之间的旋

  7. ruby - 如何修改矩阵(Ruby std-lib Matrix 类)？ - 2

    我理解RubystdlibMatrix是不可修改的，也就是说，例如。m=Matrix.zero(3,4)不会写m[0,1]=7但我非常想做...我可以用笨拙的编程来做，比如defmodify_value_in_a_matrix(matrix,row,col,newval)ary=(0...m.row_size).map{|i|m.rowi}.map(&:to_a)ary[row][col]=newvalMatrix[*ary]end...或者作弊，比如Matrix.send:[]=,0,1,7但我想知道，这一定是人们一直遇到的问题。有没有一些标准的、习惯的方法可以做到这一点，而不必使用

  8. 线性代数让我想想：快速求三阶矩阵的逆矩阵 - 2

    快速求三阶矩阵的逆矩阵前言一般情况下，我们求解伴随矩阵是要注意符号问题和位置问题的（如下所示）A−1=1[  ][−[  ]−[  ]−[  ]  −[  ]]=A−1=1[  ][   M11−[M12]   M13−[M21]   M22−[M23]     M31−[M32]   M33]⊤\begin{aligned}&A^{-1}=\frac{1}{[\\]}\left[\begin{array}{cccccc}&-[\\]&\\-[\\]&&-[\\]\\\\&-[\\]&\\\end{array}\right]=\\\\&A^{-1}=\frac{1}{[\\]}\left[\b

  9. 相机校准—外参矩阵 - 2

    在本文中，我们将探讨摄影机的外参，并通过Python中的一个实践示例来加强我们的理解。相机外参摄像头可以位于世界任何地方，并且可以指向任何方向。我们想从摄像机的角度来观察世界上的物体，这种从世界坐标系到摄像机坐标系的转换被称为摄像机外参。那么，我们怎样才能找到相机外参呢？一旦我们弄清楚相机是如何变换的，我们就可以找到从世界坐标系到相机坐标系的基变换的变化。我们将详细探讨这个想法。具体来说，我们需要知道相机是如何定位的，以及它在世界空间中的位置，有两种转换可以帮助我们：有助于确定摄影机方向的旋转变换。有助于移动相机的平移变换。让我们详细看看每一个。旋转通过旋转改变坐标让我们看一下将点旋转一个角度

  10. ruby - Ruby 中的有限矩阵 - 2

    为什么Matrix类没有方法来编辑它的向量和组件？似乎矩阵中的所有内容都可以读取但不能写入。我错了吗？是否有一些类似于Matrix的第三方优雅类允许我删除行并有意地编辑它们？如果没有这样的类(class)，请通知我——我将停止搜索。 最佳答案 Matrix类的设计者一定是不可变数据结构和函数式编程的爱好者。是的，你是对的。无论如何，总有一个简单的解决方案可以满足您的需求。使用Matrix它可以做的事情，然后，只需使用.to_a来获得一个真正的数组。>>Matrix.identity(2).to_a=>[[1,0],[0,1]]另见N

随机推荐