Java?C++?leetcode面試零矩陣

更新時(shí)間：2022年10月17日 11:52:47 作者：AnjaVon

這篇文章主要為大家介紹了Java?C++題解leetcode面試零矩陣示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路：模擬

定義兩個(gè)數(shù)組分別記錄每行or每列中為0的元素；
0所在的行列清零也就意味著元素所在行or列有0則置零【廢話連篇】；
所以一次遍歷找出有0的行列，一次遍歷根據(jù)其將相應(yīng)元素置零。

Java

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        boolean[] rows = new boolean[n], cols = new boolean[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0)
                    rows[i] = cols[j] = true;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (rows[i] || cols[j])
                    matrix[i][j] = 0;
        }
    }
}

時(shí)間復(fù)雜度：O(n×m)
空間復(fù)雜度：O(n+m)

C++

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        bool rows[n], cols[m];
        memset(rows, 0, sizeof(rows));
        memset(cols, 0, sizeof(cols));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0)
                    rows[i] = cols[j] = true;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (rows[i] || cols[j])
                    matrix[i][j] = 0;
        }
    }
};

時(shí)間復(fù)雜度：O(n×m)
空間復(fù)雜度：O(n+m)

Rust

impl Solution {
    pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
        let (n, m) = (matrix.len(), matrix[0].len());
        let (mut rows, mut cols) = (vec![false; n], vec![false; m]);
        for i in 0..n {
            for j in 0..m {
                if matrix[i][j] == 0 {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for i in 0.. n {
            for j in 0..m {
                if rows[i] || cols[j] {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

時(shí)間復(fù)雜度：O(n×m)
空間復(fù)雜度：O(n+m)

總結(jié)

因?yàn)槭侵械阮}所以糾結(jié)了半天是不是有什么精巧奇妙的算法解題……emmmm結(jié)果就只是通過修改給出數(shù)組來標(biāo)記，空間復(fù)雜度能降到常數(shù)了，有意義但不大

以上就是Java C++ leetcode面試零矩陣的詳細(xì)內(nèi)容，更多關(guān)于Java C++ 面試零矩陣的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

相關(guān)文章

C++常見的stl容器與相關(guān)操作示例解析
所謂容器，就是可以承載，包含元素的一個(gè)器件，它是STL六大組件之一，是容器、算法、迭代器中最重要也是最核心的一部分
2022-10-10
C語言實(shí)現(xiàn)輸入任意多個(gè)整數(shù)
這篇文章主要介紹了C語言實(shí)現(xiàn)輸入任意多個(gè)整數(shù)，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧
2020-12-12
C語言中全局變量,局部變量,靜態(tài)局部變量的區(qū)分方式
這篇文章主要介紹了C語言中全局變量,局部變量,靜態(tài)局部變量的區(qū)分方式,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2024-08-08
C++基于特征向量的KNN分類算法
這篇文章主要為大家詳細(xì)介紹了C++基于特征向量的KNN分類算法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-12-12
C++ OpenCV實(shí)現(xiàn)像素畫的示例代碼
這篇文章主要介紹了通過OpenCV進(jìn)行圖片像素的變化，從而形成像素畫效果的功能。文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以動(dòng)手試一試
2022-01-01
Qt6.0+vs2019環(huán)境配置的實(shí)現(xiàn)教程
這篇文章主要介紹了Qt6.0+vs2019環(huán)境配置的實(shí)現(xiàn)教程，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-03-03
C語言中extern詳細(xì)用法解析
這篇文章主要介紹了C語言中extern詳細(xì)用法解析,本文講解的extern也是C語言中的關(guān)鍵詞,用來修飾函數(shù)聲明或變量等,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07
Qt?QDateTime計(jì)算時(shí)間差的實(shí)現(xiàn)示例
本文主要介紹了Qt?QDateTime計(jì)算時(shí)間差的實(shí)現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2023-04-04
C++、Qt分別讀寫xml文件的方法實(shí)例
Qt提供了QDomElement 類用于完成對xml文件的讀取和寫入,這篇文章主要給大家介紹了關(guān)于C++、Qt分別讀寫xml文件的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
2023-03-03
C語言創(chuàng)建鏈表錯(cuò)誤之通過指針參數(shù)申請動(dòng)態(tài)內(nèi)存實(shí)例分析
這篇文章主要介紹了C語言創(chuàng)建鏈表錯(cuò)誤之通過指針參數(shù)申請動(dòng)態(tài)內(nèi)存,是鏈表創(chuàng)建過程中非常常見的經(jīng)典錯(cuò)誤。實(shí)例中做了較為詳盡的分析,需要的朋友可以參考下
2014-09-09