找到表示行方式排序矩阵中最小整数的行

Question

在最近的Java电话采访中我被问到这个问题:

您将获得具有以下属性的NxN二进制(0-1)矩阵:

• 每行都排序(序列为0,后跟1的序列)
• 每行代表一个无符号整数(通过读取位)
• 每行都是独一无二的

例:

0 1 1
1 1 1
0 0 1

每行中的位值被排序,行表示整数3,7和1.

找到表示最小整数的行.在上面的示例中,答案是第3行,它表示整数1.

我从二次复杂的蛮力开始.采访者回答说我没有利用排序的财产.

在思考了很多之后,我在每一行都使用了二元搜索,然后它来到了O(nlogn).他问我是否可以进一步改进.我想了很多但没有改进.

如果有人能提出任何关于改进它的指示,我将不胜感激.

另一个例子:

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

答案是第3行,代表整数0.

Answer 1

从第1行开始.向右走,直至找到第一行1.然后转到第2行,但保持在同一列中并重复向右走直到你遇到a 1.反复这样做.你上次走右路的那一行是你的答案.

这是O(N + M)解(对于NxM矩阵,或对于问题中给出的方形NxN矩阵的O(N)).

使用你的例子:

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

.这里的's代表遍历的路径:

. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .

该解决方案适用于非方矩阵,保留了NxM矩阵的最坏情况O(N + M)效率.

为什么这样做？保证数字将被排序意味着每一行将是一系列的0,然后是一系列的1.因此,行的大小相当于在达到1之前你可以走多远.因此,如果一行可以通过跟随0来进一步延伸,那么它必须比我们之前处理的任何东西都长.

Python代码:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

ans, j = 0, 0
for i, row in enumerate(li):
  while j < len(row) and row[j] == 0:
    j += 1
    ans = i

print "Row", ans+1, "".join(map(str, li[ans]))

还有一个更简单的解决方案,因为总是具有方形NxN矩阵和不同行的约束.它们一起意味着具有最低值的行将是0 0 ... 0 1或者0 0 ... 0 0.这是因为在矩阵中表示N + 1个可能的数字,因此"缺失"数字为0(在这种情况下,表示的最小值为1)或者它是其他的(最小值为0).

有了这些知识,我们检查右边的第二列为0.当我们找到一个时,我们向右看,如果它包含另一个0,我们得到了答案(只有一行以a结尾0).否则,我们继续在列中搜索另一个0.如果我们找不到另一个0,我们找到的第一个是我们正在寻找的行(只能有一行结束01,因为没有结束00,这是最小的).

Python代码:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

for i, row in enumerate(li):
  if row[-2] == 0:
    ans = i
    if row[-1] == 0:
      break

print "Row", ans+1, "".join(map(str, li[ans]))

该解决方案在O(N)中以较少的难度回答了该问题,但是将其概括为处理非平方NxM矩阵或非不同数字将使其最坏情况效率O(N ^ 2).我个人更喜欢第一种解决方案.

Answer 2

最小的数字必须是0或1.(因为没有重复,行被排序).所有你需要做的就是回到最后一列,如果ti包含0,则最低数字为0,否则最低数字为1.

编辑 - 解释
在N具有约束的行中,可以存在最多的N+1唯一值.
所以肯定至少0或1必须在矩阵中....

编辑2 - 算法

//assuming the matrix is 0 indexed base
for i = 0...N-1
  if M[i][N-1] == 0
    return "Value is 0 in row i";
for i = 0...N-1
  if M[i][N-2] == 0
    return "Value is 1 in row i";
//because of the explanation above the flow will never reach here.

Answer 3

由于号是唯一的,并且由于数字进行排序,这是很清楚的是对于N的任何值,最小数目可以是[随后1 0(N-1次)]或0(N次)的形式的.

例如,对于N = 4,最小的数字可以是0001或0000.

换句话说,我们希望找到的数字的倒数第二个数字为0.并且最后一个数字可以是0或1

然后,这个问题简化为只在数组中找到这些模式,这可以使用简单的for循环来完成

int rowNum = -1;

for(int i=0;i<N;i++)
{
    if(arr[i][N-2]==0) //Second last digit is 0. Hence the number could be min.
    {
        rowNum = i;

        if(arr[i][N-1]==1) // If number of the form 0001 was found, keep looking for 0000
        {
            continue;
        }
        else
         //If number of the form 0000 was found, exit. 
         //No other number can be lesser than 0000
        {
            break;
        }
    }
}
return rowNum;

该算法具有复杂度O(n)

Answer 4

您想要查找具有最大零数的行.

• 从...开始 arr[0][0]
• 如果是0,请检查右侧的元素,arr[0][1].
• 如果不是,0则跳过该行并开始检查当前元素下面的下一行中的元素.

继续做,直到你越过最后一行/最后一列,或者你找到一个全零的行.

算法:

i = 0 
j = 0 
answer = 0 

# continue till i is a valid index.
while(i<N) 

        # continue till j is valid index and ele is 0.
        while(j < N AND arr[i][j] == 0)

                # move towards right.
                j++ 

                #update answer.
                answer = i 

                # found a row with all zeros.
                if(j == N)  
                        break all loops.
                end-if

        end-while

        # skip current row..continue on next row.    
        i++ 

end-while

print answer

所述的这种复杂性是O(N+N)其是O(N),这是线性的.

Java实现

相关问题哪个使用完全相同的技巧

如何有效地搜索有序矩阵？

Answer 5

以相反的顺序循环每一行并检查 1 结束和 0 开始的位置怎么样？

事实上，可以保证在 中NxN，最坏的情况是 0 不会出现。因此，您只需检查每行的最后 2 个条目即可。这使得它呈线性。

由于我的解释不被理解，这里用伪代码表示：

int lowestRow = -1;
for (k = 0; k < array.length; k ++) {
   byte[] row = array[k];
   if (row[row.length - 1] == 0) {
       lowestRow = k;
       break;
   }
   if (row[row.length - 2] == 0) {
       lowestRow = k;
       //possibly look for all-zeroes, so not breaking
   }
}