2D陣列只有0或1

Question

我有隨機包含0或1

值的2維陣列如何I（最有效地）確定的值1（最大行迭代最下的元素i ）和最右邊的元素（最高列迭代j）？

例如：

0 0 1 0 
1 0 1 0 
0 1 0 0 
1 0 0 0 

我的程序應該回答I = 3（假設第一行爲i = 0）和J = 2（假設第一列是0）。

Answer 1

這裏有一個想法：

1. 與最底排開始，用memrchr找到每行的最後一個1（我有點假設你存儲的數字作爲char又名8位整數）。
2. 最終你會發現一排有1。這是你的答案i。由於C使用行優先順序，因此我們使用緩存友好的一次一行操作獲得了這一點。
3. 以上，您現在也知道j的下限（因爲您在最後一行中找到了最後一個1，它有任何1 s）。
4. 對於其餘行，請使用memrchr從j的下限之後的一個到每行的末尾。如果您在那裏發現任何1，請更新下限。重複，直到你檢查了所有的行。
5. 當然，如果您在最後一欄中找到1，您可以立即停止。

Answer 2

使用一個簡單的循環，並從頭開始（或結束，取決於你想要達到的目標），並檢查每個元素。沒有更有效的方法。

就C和C++而言，什麼是有效的，哪些不在於實現的本質。例如，如果這是一個位域矩陣，那麼您可以通過首先將每個字節與0進行比較來優化代碼，然後再開始搜索各個位。

和往常一樣，沒有說明它的含義，談論效率是沒有意義的。速度？內存消耗？節目大小？在沒有給定系統的情況下討論C或C++的高效實現也沒有意義。

Answer 3

以下是天真的方法 - 只是遍歷數組中的所有位置。最壞情況O（n * m）：

#define WIDTH 4 
#define HEIGHT 4 

int main() 
{ 
    int i,j,col,row; 
    int arr[HEIGHT][WIDTH] = set_Array(); 
    for (j=0;j<HEIGHT;j++){ 
     for (i = 0; i<WIDTH; i++){ 
      if (arr[j][i]){ 
       row = j>row?j:row; 
       col = i>col?i:col; 
    }}} 
} 

我們應該如何改進？那麼我們可以從最後開始並向後工作，但是我們必須交替地進行行和列，而不是輪流訪問每個單元格。我們可以尋找專欄，然後排隊，但效率不高。

0. 1. 2. 3. 
0. 0 0 1 0 
1. 1 0 1 0 
2. 0 1 0 0 
3. 1 0 0 0 

在這個例子中，我們搜索行3和列3第一，並在搜索消除它們。然後行2和列2直至但不包括被刪除的列3和行3。然後行1 ...
當然，當找到包含1的最下面一行時，我們停止搜索行，並在找到包含1的最右面一行時停止搜索列。

代碼：

#include <stdio.h> 

#define WIDTH 4 
#define HEIGHT 4 

int main() 
{ 
    int i,j,col = 0, row = 0; 
    int current_row = HEIGHT; 
    int current_col = WIDTH; 
    int arr[WIDTH][HEIGHT] = {{0,0,1,0},{1,0,1,0},{0,1,0,0},{1,0,0,0}}; 
    while (!(row && col)) 
    { 
     current_row--; 
     current_col--; 
     if (!row){ 
      printf("searching row: %d\n",current_row); 
      for (i = 0; i < current_col; i++){ 
       if (arr[current_row][i]){ 
         row = current_row; 
     }}} 
     if (!col){ 
      printf("searching col: %d\n",current_col); 
      for (j = 0; j < current_row; j++){ 
       if (arr[j][current_col]){ 
        col = current_col; 
     }}} 
    } 
    printf("col: %d, row: %d\n", col, row); 
} 

See it live

輸出：

searching row: 3 
searching col: 3 
searching col: 2 
col: 2, row: 3 

最壞的情況仍然是O（m * n個），並且實際上是略差（你測試細胞對角線從右下兩次開始），但平均情況會更好。

我們掃描最低的未搜索行爲1，然後搜索最右邊的未搜索列以獲得1。
當你找到最低1你不再搜索每行更多1的。當你找到最右邊的1時，你不再搜索每一列以尋找更多的1。

這樣我們一旦找到答案就停止搜索，而不像天真的方法，這意味着我們通常不需要經過數組中的每個值。

Answer 4

如果數組的行大小最多爲32個數字，則可以使用單個int32_t來表示整行：數字的值是整行。 然後你的整個陣列將是int32_t的一個維數組：

int32_t matrix[nRows]; 

現在你可以通過尋找matrix的最後一個數字是不等於0 O（NROWS）時間找到最下面一行一個非常簡單的實現。

此外，你可以找到最右邊的1通過下面的技巧： 對於您通過計算matrix[i] & -matrix[i]隔離最右邊各1 matrix[i]。然後計算這個結果的log2會給出列的編號。所有matrix[i]數字的最大列數可以給出您想要的結果。 （再次用一個非常簡單的實現O（nRows）時間）。

當然，如果行大小大於32個值，則必須使用每行更多的int32_t值，但原則保持不變。