Java?C++?leetcode面試零矩陣
更新時間：2022年10月17日 11:52:47 作者：AnjaVon
這篇文章主要為大家介紹了Java?C++題解leetcode面試零矩陣示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
題目要求
思路：模擬
- 定義兩個數(shù)組分別記錄每行or每列中為0的元素；
- 0所在的行列清零也就意味著元素所在行or列有0則置零【廢話連篇】；
- 所以一次遍歷找出有0的行列，一次遍歷根據(jù)其將相應元素置零。
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;
}
}
}
- 時間復雜度：O(n×m)
- 空間復雜度：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;
}
}
};
- 時間復雜度：O(n×m)
- 空間復雜度：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;
}
}
}
}
}
- 時間復雜度：O(n×m)
- 空間復雜度：O(n+m)
總結(jié)
因為是中等題所以糾結(jié)了半天是不是有什么精巧奇妙的算法解題……emmmm結(jié)果就只是通過修改給出數(shù)組來標記，空間復雜度能降到常數(shù)了，有意義但不大
以上就是Java C++ leetcode面試零矩陣的詳細內(nèi)容，更多關(guān)于Java C++ 面試零矩陣的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++替換棧中和.data中的cookie實現(xiàn)步驟詳解
這篇文章主要介紹了C++替換棧中和.data中的cookie實現(xiàn)步驟，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2022-10-10
這篇文章主要為大家詳細介紹了C語言實現(xiàn)猜數(shù)游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
C++將音頻PCM數(shù)據(jù)封裝成wav文件的方法
這篇文章主要為大家詳細介紹了C++將音頻PCM數(shù)據(jù)封裝成wav文件的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
對性能來說，許多的問題都需要和出現(xiàn)頻率及本身執(zhí)行一次的開銷掛鉤，有些問題雖然看似比較開銷較大，但是很少會執(zhí)行到，那也不會對程序有大的影響；同樣一個很小開銷的函數(shù)執(zhí)行很頻繁，同樣會對程序的執(zhí)行效率有很大影響。本章中作者主要根據(jù)臨時對象來闡述這樣一個觀點2022-04-04
在C語言中,int?類型的大小通常是根據(jù)系統(tǒng)架構(gòu)來決定的,在大多數(shù)現(xiàn)代系統(tǒng)上,int?通常是32位的,在C語言中,獲取int類型的最大值有幾種不同的方法,下面,我們將討論兩種方法：使用標準庫函數(shù)和使用算法,需要的朋友可以參考下2024-06-06
C++實現(xiàn)LeetCode(9.驗證回文數(shù)字)
這篇文章主要介紹了C++實現(xiàn)LeetCode(9.驗證回文數(shù)字),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
C語言提供了多種預處理功能,如宏定義、文件包含、條件編譯等,下面這篇文章主要給大家介紹了關(guān)于C語言進階教程之預處理的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-02-02
這篇文章主要介紹了C++ 實現(xiàn)一個復數(shù)類的實例代碼,代碼簡單易懂，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
這篇文章主要介紹了C++類常量和類枚舉，給類當中定義一些常量，可以給所有類的對象使用，比如說我們在類當中定義一個數(shù)組，希望可以定義一個常量，用來初始化數(shù)組的長度，那么下面我i嗎就來看看過程當如何吧2022-01-01
由于編譯的警告各種各樣，根本不可以一一羅列出來，下面只是列舉出比較典型的十六種警告，還有一些警告，大家只要根據(jù)字面意思，就可以很快的查找出來，并解決之。希望對大家有所幫助。2014-08-08