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é)果就只是通過(guò)修改給出數(shù)組來(lái)標(biāo)記，空間復(fù)雜度能降到常數(shù)了，有意義但不大

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

您可能感興趣的文章:

相關(guān)文章

C++替換棧中和.data中的cookie實(shí)現(xiàn)步驟詳解
這篇文章主要介紹了C++替換棧中和.data中的cookie實(shí)現(xiàn)步驟，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧
2022-10-10
C語(yǔ)言實(shí)現(xiàn)猜數(shù)游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)猜數(shù)游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-12-12
C++將音頻PCM數(shù)據(jù)封裝成wav文件的方法
這篇文章主要為大家詳細(xì)介紹了C++將音頻PCM數(shù)據(jù)封裝成wav文件的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-01-01
C++簡(jiǎn)明分析臨時(shí)對(duì)象是什么
對(duì)性能來(lái)說(shuō)，許多的問(wèn)題都需要和出現(xiàn)頻率及本身執(zhí)行一次的開銷掛鉤，有些問(wèn)題雖然看似比較開銷較大，但是很少會(huì)執(zhí)行到，那也不會(huì)對(duì)程序有大的影響；同樣一個(gè)很小開銷的函數(shù)執(zhí)行很頻繁，同樣會(huì)對(duì)程序的執(zhí)行效率有很大影響。本章中作者主要根據(jù)臨時(shí)對(duì)象來(lái)闡述這樣一個(gè)觀點(diǎn)
2022-04-04
獲取C語(yǔ)言中int類型的最大值的方法小結(jié)
在C語(yǔ)言中,int?類型的大小通常是根據(jù)系統(tǒng)架構(gòu)來(lái)決定的,在大多數(shù)現(xiàn)代系統(tǒng)上,int?通常是32位的,在C語(yǔ)言中,獲取int類型的最大值有幾種不同的方法,下面,我們將討論兩種方法：使用標(biāo)準(zhǔn)庫(kù)函數(shù)和使用算法,需要的朋友可以參考下
2024-06-06
C++實(shí)現(xiàn)LeetCode(9.驗(yàn)證回文數(shù)字)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(9.驗(yàn)證回文數(shù)字),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07
C語(yǔ)言進(jìn)階教程之預(yù)處理
C語(yǔ)言提供了多種預(yù)處理功能,如宏定義、文件包含、條件編譯等,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言進(jìn)階教程之預(yù)處理的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
2023-02-02
C++ 實(shí)現(xiàn)一個(gè)復(fù)數(shù)類的實(shí)例代碼
這篇文章主要介紹了C++ 實(shí)現(xiàn)一個(gè)復(fù)數(shù)類的實(shí)例代碼,代碼簡(jiǎn)單易懂，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2021-04-04
C++類常量和類枚舉
這篇文章主要介紹了C++類常量和類枚舉，給類當(dāng)中定義一些常量，可以給所有類的對(duì)象使用，比如說(shuō)我們?cè)陬惍?dāng)中定義一個(gè)數(shù)組，希望可以定義一個(gè)常量，用來(lái)初始化數(shù)組的長(zhǎng)度，那么下面我i嗎就來(lái)看看過(guò)程當(dāng)如何吧
2022-01-01
16種C語(yǔ)言編譯警告(Warning)類型的解決方法
由于編譯的警告各種各樣，根本不可以一一羅列出來(lái)，下面只是列舉出比較典型的十六種警告，還有一些警告，大家只要根據(jù)字面意思，就可以很快的查找出來(lái)，并解決之。希望對(duì)大家有所幫助。
2014-08-08