要應用哪個數據結構？

Question

有一個大小爲n*n的矩陣，其中n<=500000。最初，所有的元素都爲0，我們有由一定數目的每一個有輸入時更新整個行或列

例如：

n=3  
RS 1 10 

意味着我們具有由10

更新第1行

0 0 0 
0 0 0 
0 0 0 

更新後

10 10 10 
0 0 0  
0 0 0 

同我們有列做。最後我們要計算矩陣中0的個數

作爲n是非常大的二維數組無法應用。那麼應用哪種數據結構？

Answer 1

嗯，這很有趣，它當然取決於您要執行的操作的數量，但我會將它保存爲2個單維數組。一個帶有行輸入，另一個帶有列輸入。

行[n]和COL [N]

所以，當你想知道說元素（4,7）的值，這將是行[4] +山坳[7]

Answer 2

您可能需要一個內部包含std::list <std::list<int>>的用戶定義類型。

但是真的，你能同時容納250000000000個整數嗎？我對此表示懷疑！

您可能需要使用兩維整數數組的非常不同的文件到內存映射數據結構。

Answer 3

以@ Techmonk的回答遠一點：我提出兩種方法：

1. Techmonk的

O（1）的更新，爲O（n^2）用於回收的0`s

數

class matZeroCount { 
    std::vector<int> m_rows; 
    std::vector<int> m_cols; 
public: 
    matZeroCount(unsigned int n): m_rows(n, 0), m_cols(n, 0) {}; 
    void updateRow(unsigned int idx, int update) { 
      // check idx range w.r.t m_rows.size() 
      // ignore update == 0 case 
      m_rows[ idx ] += update; 
    } 
    void updateCol(unsigned int idx, int update) { 
      // check idx range w.r.t m_cols.size() 
      // ignore update == 0 case 
      m_cols[ idx ] += update; 
    } 
    unsigned int countZeros() const { 
     unsigned int count = 0; 
     for (auto ir = m_rows.begin(); ir != m_rows.end(); ir++) { 
      for (auto ic = m_cols.begin(); ic != m_cols.end(); ic++) { 
        count += ((*ir + * ic) == 0); 
      } 
     } 
     return count; 
    } 
}; 

2.快速計數

這種方法允許O（1）用於回收的零的數目，在O（n）的成本，每次更新。如果您期望少於O（n）次更新 - 此方法可能更有效。

class matZeroCount { 
    std::vector<int> m_rows; 
    std::vector<int> m_cols; 
    unsigned int  m_count; 
public: 
    matZeroCount(unsigned int n): m_rows(n, 0), m_cols(n, 0), count(0) {}; 
    void updateRow(unsigned int idx, int update) { 
      // check idx range w.r.t m_rows.size() 
      // ignore update == 0 case 
      m_rows[ idx ] += update; 
      for (auto ic = m_cols.begin(); ic != m_cols.end(); ic++) { 
       m_count += ((m_rows[ idx ] + *ic) == 0); // new zeros 
       m_count -= ((m_rows[ idx ] - update + *ic) == 0); // not zeros anymore 
      } 
    } 
    void updateCol(unsigned int idx, int update) { 
      // check idx range w.r.t m_cols.size() 
      // ignore update == 0 case 
      m_cols[ idx ] += update; 
      for (auto ir = m_rowss.begin(); ir != m_rows.end(); ir++) { 
       m_count += ((m_cols[ idx ] + *ir) == 0); // new zeros 
       m_count -= ((m_cols[ idx ] - update + *ir) == 0); // not zeros anymore 
      } 

    } 
    unsigned int countZeros() const { return m_count; }; 
}; 

Answer 4

Sparse Matrix是一種數據結構適合於用零填充大多矩陣。其實施面向空間效率。當您的信息很少的大型矩陣時，它適用於像您一樣的情況。