当前位置：首页 > article >正文

10. 九转金丹炼矩阵 - 矩阵置零（标记优化）

article 2025/2/24 22:46:11

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的金丹谷，谷中有一座巨大的九转金丹炉，炉身闪烁着神秘的光芒。金丹炉的入口处有一块巨大的石碑，上面刻着一行文字：“欲破此炉，需以九转金丹之力，炼矩阵之零，标记优化定乾坤。”

哪吒定睛一看，石碑上还有一行小字：“矩阵中，需要将包含0的行和列全部置为0。”哪吒心中一动，他知道这是一道关于矩阵置零的难题，需要找到矩阵中所有包含0的行和列，并将它们全部置为0。

[
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1]
]

暴力解法：九转金丹的初次尝试

哪吒心想：“要将矩阵中包含0的行和列置为0，我可以先记录所有包含0的行和列，然后再逐行逐列置零。”他催动九转金丹之力，从头到尾遍历矩阵，用两个集合记录所有包含0的行和列。随后，他根据这些记录将对应的行和列置为0。

void setZeroes(vector<vector<int>>& matrix) {
   
    int m = matrix.size();
    int n = matrix[0].size();
    unordered_set<int> zeroRows, zeroCols;

    // 记录包含0的行和列
    for (int i = 0; i < m; ++i) {
   
        for (int j = 0; j < n; ++j) {
   
            if (matrix[i][j] == 0) {
   
                zeroRows.insert(i);
                zeroCols.insert(j);
            }
        }
    }

    // 置零行
    for (int row : zeroRows) {
   
        fill(matrix[row].begin(), matrix[row].end(), 0);
    }

    // 置零列
    for (int col : zeroCols) {
   
        for (int i = 0; i < m; ++i) {
   
            matrix[i][col] = 0;
        }
    }
}

哪吒成功地将矩阵中包含0的行和列置为0，但九转金丹炉的光芒却黯淡了下来。他意识到，这种方法虽然可行，但需要额外的空间来存储行和列的标记，灵力消耗较大。

C++语法点：集合与矩阵操作

在C++中，集合和矩阵操作是处理矩阵问题的常用工具。以下是一些重要特性：

集合：
- unordered_set是一个基于哈希表的集合，用于存储唯一元素。
- 常用方法：
  - insert(value)：插入一个元素。
  - find(value)：查找一个元素是否存在。
矩阵操作：
- 使用vector<vector<int>>表示矩阵。
- 使用fill(start, end, value)可以将一段范围内的元素全部置为指定值。