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值，但原则保持不变。