(每日算法)LeetCode--Set Matrix Zeroes (矩陣置零)

(每日算法)LeetCode--Set Matrix Zeroes (矩陣置零)

給定一個矩陣，如果有零元素那麼就將零元素所在的行和列都置為零。

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

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

題目的難點就在於，如果遇到零元素之後馬上在矩陣上操作，將所在的行和列都置為零。在接下來的遍歷中，如果你再遇到零，你講不清楚是原矩陣的零還是你修改之後的零。所以，一種方法就是先通過兩個數組來記錄該行該列上有沒有零元素，等對矩陣遍歷完之後再統一修改即可。

class Solution {
public:
    void setZeroes(vector > &matrix) {
  
	    const size_t m = matrix.size();
	    const size_t n = matrix[0].size();
	    vector row(m, false); //標記該行是否存在0
	    vector col(n, false);
	    
	    for(int i = 0; i < matrix.size(); i++)
	    {
	    	for(int j = 0; j < matrix[0].size(); j++)
		{
			if(matrix[i][j] == 0)
				row[i] = col[j] = true;//如果原矩陣中存在0，記錄該行和列的位置。
		}
	    }

	 for (size_t i = 0; i < m; ++i) {
		if (row[i])
			fill(&matrix[i][0], &matrix[i][0] + n, 0);//將矩陣的一行置為零
		}
	for (size_t j = 0; j < n; ++j) {
		if (col[j]) {
			for (size_t i = 0; i < m; ++i) 
				matrix[i][j] = 0;//將矩陣的一列置為0
		       	}
	}
    }
};

fill函數的作用是：將一個區間的元素都賦予val值。函數參數：fill(first,last,val);//first為容器的首迭代器，last為容器的末迭代器，val為將要替換的值。

作用和下面的函數相同:

template 
  void fill (ForwardIterator first, ForwardIterator last, const T& val)
{
  while (first != last) {
    *first = val;
    ++first;
  }
}

使用fill函數的一個例子：

// fill algorithm example
#include      // std::cout
#include     // std::fill
#include        // std::vector

int main () {
  std::vector myvector (8);                       // myvector: 0 0 0 0 0 0 0 0

  std::fill (myvector.begin(),myvector.begin()+4,5);   // myvector: 5 5 5 5 0 0 0 0
  std::fill (myvector.begin()+3,myvector.end()-2,8);   // myvector: 5 5 5 8 8 8 0 0

  std::cout << "myvector contains:";
  for (std::vector::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

輸出是：myvector contains: 5 5 5 8 8 8 0 0

fill_n函數的作用是：給你一個起始點，然後再給你一個數值count和val。把從起始點開始依次賦予count個元素val的值

相當於下面的函數：

template 
  OutputIterator fill_n (OutputIterator first, Size n, const T& val)
{
  while (n>0) {
    *first = val;
    ++first; --n;
  }
  return first;     // since C++11
}

在C++11中返回首迭代器的值，在c++98中什麼都不返回。n在98中不能為負數，在11中，如果為負數，則什麼也不做。

一個例子：

// fill_n example
#include      // std::cout
#include     // std::fill_n
#include        // std::vector

int main () {
  std::vector myvector (8,10);        // myvector: 10 10 10 10 10 10 10 10

  std::fill_n (myvector.begin(),4,20);     // myvector: 20 20 20 20 10 10 10 10
  std::fill_n (myvector.begin()+3,3,33);   // myvector: 20 20 20 33 33 33 10 10

  std::cout << "myvector contains:";
  for (std::vector::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

這也就引出來指針和迭代器的區別：

相同點---指針和iterator都支持與整數進行+，-運算，而且其含義都是從當前位置向前或者向後移動n個位置；指針和iterator都支持減法運算，指針-指針得到的是兩個指針之間的距離，迭代器-迭代器得到的是兩個迭代器之間的距離； 通過指針或者iterator都能夠修改其指向的元素。

不同點--- cout操作符可以直接輸出指針的值，但是對迭代器進行在操作的時候會報錯。通過看報錯信息和頭文件知道，迭代器返回的是對象引用而不是對象的值，所以cout只能輸出迭代器使用*取值後的值而不能直接輸出其自身； 指針能指向函數而迭代器不行，迭代器只能指向容器。

指針是一種特殊的變量,它專門用來存放另一變量的地址，而迭代器只是參考了指針的特性進行設計的一種STL接口。

網上有這樣一種說法：迭代器是廣義指針，而指針滿足所有迭代器要求。迭代器是STL算法的接口，而指針是迭代器，因此STL算法可以使用指針來對基於指針的非STL容器進行操作。

也許某些編譯器使用指針來實現迭代器以至於有些人會誤以為指針和迭代器是一個概念來的。

迭代器並不是普通的指針，可以說是智能指針。只有在vector容器中Iterator才是普通的指針。其他情況Iterator都是比較復雜的數據就夠。Iterator分為了只讀、只寫、向前、雙向和隨機訪問五種不同的類型。根據容器的不同和使用的情況，Iterator使用不同的類型。像List就是雙向的Iterator。所有的Iterator都符合左閉右開的原則。