@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; };
};