程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Set Matrix Zeroes

leetcode筆記:Set Matrix Zeroes

編輯:關於C++

一.題目描述

Given a m*n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

二.題目分析

該題目最直觀的解法就是開辟一個新的矩陣,當原矩陣存在零元素的時候,就將新矩陣的對應行和列置為零。這樣空間復雜度較高,也是題目不允許的。

若要做到空間復雜度為常數,我的做法是就是利用矩陣的第一行和第一列來作為標記使用,這樣便不用開辟新的存儲空間。具體方法:

先確定第一行和第一列是否需要清零,即:遍歷第一行中是否有0,也同時記下第一列中有沒有0。在以下代碼中,使用bool型變量x_keyy_key分別記錄第一行和第一列的情況;

掃描剩下的矩陣元素,如果遇到了0,就將該元素所對應的第一行和第一列上的元素賦值為0

在遍歷完二維數組後,就可以根據第一行和第一列的信息,將剩下的矩陣元素進行賦值。拿第一行為例,如果掃描到第i個元素為0,就將二維數組的第i列全部置0

最後,根據1中bool型變量x_keyy_key的值,處理第一行和第一列。如果最開始得到的第一行中有0的話,就整行清零,對第一列也采取同樣的處理。

三.示例代碼

第一種方法如下:

#include 
using namespace std;

class Solution
{
public:
    // 時間復雜度O(m * n),空間復雜度O(m + n)
    void setZeros(vector >& matrix)
    {
        const size_t x = matrix.size();
        const size_t y = matrix[0].size();
        if (x == 0 || y == 0) return;
        vector rowRes(x, false);
        vector colRes(y, false);

        for (size_t i = 0; i < x; i++)
        {
            for (size_t j = 0; j < y; j++)
            {
                if (matrix[i][j] == 0)
                    rowRes[i] = colRes[j] = true;
            }
        }

        // set zero
        for (size_t i = 0; i < x; i++)
        {
            if (rowRes[i])
                for (size_t k = 0; k < x; k++)
                    matrix[i][k] = 0;
        }
        for (size_t j = 0; j < y; j++)
        {
            if (colRes[j])
                for (size_t k = 0; k < x; k++)
                    matrix[k][j] = 0;
        }
    }
};

以上方法的空間復雜度為O(m + n),並不能達到題目要求的最終要求。

第二種方法如下:

#include 
using namespace std;

class Solution
{
public:
    void setZerosBetter(vector >& matrix)
    {
        const size_t x = matrix.size();
        const size_t y = matrix[0].size();
        bool x_key = false, y_key = false;
        if (x == 0 || y == 0) return;

        for (size_t i = 0; i < y; i++)
        {
            if (matrix[0][i] == 0)
            {
                x_key = true;
                break;
            }
        }

        for (size_t i = 0; i < x; i++)
        {
            if (matrix[i][0] == 0)
            {
                y_key = true;
                break;
            }
        }

        for (size_t i = 0; i < x; i++)
        {
            for (size_t j = 0; j < y; j++)
            {
                if (matrix[i][j] == 0 && i > 0 && j > 0)
                {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 調整1~x行、1~y列的元素
        for (size_t i = 1; i < x; i++)
            if (matrix[i][0] == 0)
            {
                for (size_t k = 1; k < y; k++)
                    matrix[i][k] = 0;
            }
        for (size_t j = 1; j < y; j++)
            if (matrix[0][j] == 0)
            {
                for (size_t k = 1; k < x; k++)
                    matrix[k][j] = 0;
            }

        // 最後調整第一行第一列

        if (y_key)
            for (size_t k = 0; k < x; k++)
                matrix[k][0] = 0;

        if (x_key)
            for (size_t k = 0; k < y; k++)
                matrix[0][k] = 0;
    }
};

四.小結

這道題如果只是僅僅想實現功能的話,不需要什麼技巧,只有提高對空間復雜度的要求才能體現出算法設計的思想。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved