2

有一个大小矩阵在n*n哪里n<=500000。最初所有元素都是 0。每次有输入时，我们必须将整行或整列更新一定数量

例子：

n=3    
RS 1 10

意味着我们必须将第 1 行更新 10

0 0 0
0 0 0
0 0 0

更新后

10 10 10
 0  0  0    
 0  0  0

我们必须为列做同样的事情。最后，我们必须计算矩阵中 0 的数量

因为n不能应用非常大的二维数组。那么应用哪种数据结构呢？

4

4 回答 4

4

Well this is interesting, it would ofcourse depend on the number of operations you are going to perform but I would save it as 2 single dimension arrays. One with the row inputs and the other with the column inputs.

row[n] and col[n]

So the when you want to know the value of say element (4,7) it would be row[4] + col[7]

于 2013-02-05T11:50:58.910 回答
3

进一步考虑@Techmonk 的回答：我提出了两种方法：

1. Techmonk的

O(1) 用于更新，O(n^2) 用于恢复 0 的数量

 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; };
 };
于 2013-02-05T12:26:19.083 回答
3

稀疏矩阵是一种适用于大多数填充为零的矩阵的数据结构。它的实施以空间效率为导向。它适用于像您这样的情况，当您拥有信息量很少的大型矩阵时。

于 2013-02-05T12:44:31.633 回答
1

您可能需要一个内部包含std::list <std::list<int>>.

但实际上，你能在内存中同时保存 250000000000 个整数吗？我对此表示怀疑！

您可能需要使用一个非常不同的、文件到内存映射的二维整数数组数据结构。

于 2013-02-05T11:51:26.843 回答