一個N*N的矩陣，取值為0或1，有什麼好的演算法判斷一行或一列全為1啊？

---

0/1取值， 可以用Bit來存儲表示
假如N=32
可以用一個unsigned int變數來存儲一行的32個狀態值
那麼判斷一行全為1， 就變成了判斷這個unsigned int 是否等於一個常數的操作了
a == 0xffffffff
隨著N的大小，可以用不同的長度的Bit位來存儲和判斷

如果題目變換為，一行有N-2個1這類問題
可以繼續使用Bit的存儲方式
使用GCC有內建的函數__builtin_popcount 可以用來統計1的個數

---

首先要搞明白這是一個實際問題還是一個智力問題。如果是實際問題，解決方案的種類和難度隨實際情況不同。例如，你完全可以用一個額外 field 來標明此行是否全為 0：這樣會 set-zero 操作在最差的情況下會變為原來的 N 倍。所以這個方法取決於你的三種操作 (set-one, set-zero, read) 的概率。

---

首先，你輸入一個矩陣並且保存它，複雜度就要O(N^2)，這個是最低要求了。
如果你是要隨時修改矩陣中的某個點的值，然後隨時詢問某一行是否為0為1的話。用兩個數組分別記錄某一行的和或者某一列的和。那麼修改某一個&元素的值時，相應的修改i行的和還有j列的和。這樣，每次詢問就O(1)直接得到答案了。

---

每一行邏輯與吧，比加法活著乘法的效率都要高點,其他和@王華庚一樣的

---

template&
class Matrix {
std::bitset& rows_[N];
std::bitset& columns_[M];
public:
void Set(int r, int c, bool v) {
rows_[r].set(c, v);
columns_[c].set(r, v);
}

bool IsRowAllZero(int r) {
return rows_[r].empty();
}

bool IsColumnAllZero(int c) {
return columns_[c].empty();
}
};


沒測試過，大意如此。
如果希望運行時確立矩陣大小，那就用vector&。

---

如果追求演算法效率的話，那就是少用循環跳轉，最簡單的辦法就是 每行相加是否等於N；或者相乘是否等於0；否則就結束判斷。並記錄0點行列，想對應的其他列就不需要判斷了。

---

可不可以用矩陣乘法？已知N*N矩陣A，構建N*N全為1矩陣B，用AXB，判斷結果中（n-1，n-1）0&個人覺得這個更多的是一個數據結構涉及的問題了，而不是演算法的問題。對於行列比較少的矩陣可以考慮結構體的位域來存放矩陣的一行或一列；對於行列比較多的話，可以考慮多個長整形的變數的位組合表示一行或一列，再組合成一個數組表示矩陣。這樣的話，判斷某一行或某一列只需用全1組成的矩陣行或列進行位與操作即可。

---

其實要記狀態的話可以直接記在第一個格子裡面。。。因為如果全1了那麼第一格必定是1，如果不全1——那麼第一格寫成1又有啥用呢？於是有O(1)時間複雜度，不用空間的記狀態方法。

---

數據沒有規律的話，那隻能訪問所有元素，如果規模不大，可以存為若干長整型，然後位運算。

---

開個對應空間，利用指針讀取相應的長度該空間的值，判斷這個值就好了。

---

若A為待處理矩陣，sum(A)後得到一向量B，然後用find(B==N)找出所有

---

推薦閱讀：