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では、非常に大きな 2 次元配列は適用できません。では、どのデータ構造を適用するのでしょうか?

4

4 に答える 4

4

これは興味深いことです。もちろん、実行する操作の数によって異なりますが、2 つの 1 次元配列として保存します。1 つは行入力、もう 1 つは列入力です。

行[n]と列[n]

したがって、たとえば要素 (4,7) の値を知りたい場合は、row[4] + col[7] になります。

于 2013-02-05T11:50:58.910 に答える
3

スパース行列は、ほとんどがゼロである行列に適したデータ構造です。その実装は、スペース効率に向けられています。情報がほとんどない大きな行列がある場合のように、これは適切です。

于 2013-02-05T12:44:31.633 に答える
3

@Techmonkの回答をもう少し進めます。2つのアプローチを提案します。

1. テクモンクス

更新の場合は O(1)、0 の数を回復する場合は O(n^2)

 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(n) のコストで O(1) の数のゼロを回復できます。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 に答える
1

を内部に含むユーザー定義型が必要になる場合がありますstd::list <std::list<int>>。

しかし、実際には、同時に 250000000000 個の整数をメモリに保持できますか? 疑わしい！

整数の 2 次元配列のファイルからメモリへのマップ データ構造を使用する必要がある場合があります。

于 2013-02-05T11:51:26.843 に答える