当前位置： 文江博客话题详情

找到代表按行排序矩阵中最小整数的行

发布于 2024-10-04 23:08:47 字数 540 浏览 7 评论 0原文

在最近的一次 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。

原文

I was asked this question on in a recent Java telephonic interview:

You are given an NxN binary (0-1) matrix with following properties:

  • Each row is sorted (sequence of 0's followed by sequence of 1's)
  • Every row represents an unsigned integer (by reading the bits)
  • Each row is unique

Example:

0 1 1
1 1 1
0 0 1

The bit values in each row is sorted and the rows represent the integers 3, 7 and 1.

Find the row representing the smallest integer. In the example above, the answer is row 3, which represents the integer 1.

I started with brute force of quadratic complexity. The interviewer replied saying I was not exploiting the sorted property.

After thinking a lot I used binary search on each row and it came to O(nlogn). He asked if I could improve any further. I thought a lot but failed to improve.

I would appreciate if anyone can give any pointers on imporoving it.

Another example:

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

The answer will be row 3, which represents the integer 0.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（14）

蓬勃野心 2024-10-11 23:08:47

从第 1 行开始。向右走，直到到达第一个 1。然后向下移动到第 2 行，但保持在同一列中，并重复向右移动的过程，直到遇到 1。重复执行此操作。您最后一次向右迈出的那一行就是您的答案。

这是一个 O(N+M) 解决方案（对于 NxM 矩阵，或者对于问题中给出的 NxN 方阵来说是 O(N)）。

使用您的示例：

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

这里的 . 代表遍历的路径：

. . 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，我们就得到了答案（只能有一行以 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)。我个人更喜欢第一种解决方案。

Start with row 1. Go right until you hit the first 1. Then go down to row 2, but remain in the same column and repeat the process of going right until you hit a 1. Do this repeatedly. The row in which you last stepped right is your answer.

This is an O(N+M) solution (for an NxM matrix, or O(N) for a square NxN matrix as given in the question).

Using your example of:

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

The .'s here represent the path traversed:

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

This solution works on non-square matrixes, retaining a worst case O(N+M) efficiency for an NxM matrix.

Why does this work? The guarantee that the numbers will be sorted means every row will be a series of 0's followed by a series of 1's. So the magnitude of a row is equivalent to how far right you can go before hitting a 1. So if a row can ever take you further by just following the 0's, then it must be longer than anything we've processed before.

Python code:

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]))

There is also a simpler solution, because of the constraints of always having a square NxN matrix and distinct rows together. Together they mean that the row with the lowest value will be either 0 0 ... 0 1 or 0 0 ... 0 0. This is because there are N of N+1 possible numbers represented in the matrix, so the "missing" number is either 0 (in which case the smallest value represented is 1) or it's something else (smallest value is 0).

With this knowledge, we check the column second from the right for a 0. When we find one, we look to its right and if that contains another 0 we have our answer (there can only be one row ending in a 0). Otherwise, we continue to search the column for another 0. If we don't find another 0, the first one we found was the row we're looking for (there can only be one row ending in 01 and since there was none ending in 00, this is the smallest).

Python code:

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]))

That solution answers the question with least difficulty in O(N), but generalising it to handle non-square NxM matrixes or non-distinct numbers will make its worst-case efficiency O(N^2). I personally prefer the first solution.

回复 原文
起风了 2024-10-11 23:08:47

最小的数字必须是 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.

the lowest number must be 0 or 1. (because there are no duplications and the rows are sorted). all you have to do is go over the last column, if ti contains 0 lowest number is 0 else lowest number is 1.

EDIT - explanation
In N rows with the constraint you sated there can be a maximum of N+1 unique values.
so for sure at least 0 or 1 must be in the matrix....

Edit 2 - algorithm

//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.
回复 原文
海夕 2024-10-11 23:08:47

由于数字是唯一的并且数字已排序，因此很明显，对于任何 N 值，最小数字可以采用 [0（N-1 次）后跟 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)

Since the numbers are unique and since the digits are sorted, it is quite clear that for any value of N, the smallest number can be either of the form [0(N-1 times) followed by 1] or 0(N times).

For example, for N=4, the smallest number
can either be 0001 or 0000.

In other words, second last digit of the number we wish to find HAS to be 0. And the last digit can either be 0 or 1

This problem then reduces to just finding these patterns in the array, which can be done using a simple for loop

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;

This algorithm would have complexity O(n)

回复 原文
你不是我要的菜∠ 2024-10-11 23:08:47

您想要找到零数量最多的行。

  • 从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实现

相关问题完全相同的技巧

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

You want to find a rows with maximum number of zeros.

  • Start at arr[0][0]
  • If it is 0, check the element towards
    right of it, arr[0][1].
  • If it's not 0 then skip that row and
    start checking at the element in the
    next row below the current element.

Keep doing till you go past the last row/last column or you find a row with all zeros.

Algorithm:

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

The complexity of this is O(N+N) which is O(N), that is linear.

Java implementation

Related question Which makes use of exact same trick

How to efficiently search in an ordered matrix?

回复 原文
梦里梦着梦中梦 2024-10-11 23:08:47
Start at the top-left.

The first row is the best row so far.

Repeat until you reach the bottom:
  If you're not already over a 1:
    Go right until you find a 1.
    This row is the best row so far.
  Go down one row.

Report the best row that was found.

你永远不会向上或向左 - 你只会向下 (n-1) 次，并且向右不超过 (n-1) 次，因此时间复杂度为 O(n)。这通过认识到您永远不必向左检查 1 来利用排序性 - 如果左侧某处有 1，则当前位置也有 1（因此该行中的数字至少为与前一行中的一样大）。

Start at the top-left.

The first row is the best row so far.

Repeat until you reach the bottom:
  If you're not already over a 1:
    Go right until you find a 1.
    This row is the best row so far.
  Go down one row.

Report the best row that was found.

You never go up or left - you only go down (n-1) times and right no more than (n-1) times, making this O(n). This exploits the sortedness by realizing that you never have to go left to check for a 1 - if there is a 1 somewhere to the left, then there is also a 1 in the current spot (and thus the number in this row is at least as big as the one in the previous row).

回复 原文
神经暖 2024-10-11 23:08:47

由于每行中的位都是排序的，因此一旦找到 1 位，右侧的所有位也必须为 1。换句话说，该数组仅存储 2^n-1 形式的值。

所以答案是零条目最多的行是最小的。

然而，由于只能存在 2**m-1 个条目，并且其中有 n 个，并且没有两个是相同的，因此我们可以推断出更多 - 对于任何 N 都有 N+1 个这样的值。因此 0 或 1 必须存在，因为我们知道没有重复项。

因此，寻找一个空行（只有最右边的零列）。如果没有找到，则答案为 1，否则为 0。O

(N)

Since the bits in each row are sorted, once you have found a 1 bit, all bits to the right must be 1 too. In other words, the array only stores values of the form 2^n-1.

So the answer is the row with the most zero entries is the smallest.

However, since only 2**m-1 entries can be present, and there are n of those, and no two are the same we can deduce more - for any N there are N+1 such values. So either 0 or 1 must be present as we know there are no duplicates.

So look for an empty row (which is hte only one with rightmost column zero). If you don't find it, the answer is 1, else it's 0.

O(N)

回复 原文
我一向站在原地 2024-10-11 23:08:47

以相反的顺序循环每一行并检查 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
   }
}

How about looping each line in reverse order and checking where the 1s end and the zeroes start?

In fact it is guaranteed that in NxN, the worst case is that 0 won't be there. So you can just check the last 2 entries of each row. Which makes it linear.

Since my explanation was not understood, here it is in somewhat pseudo code:

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
   }
}
回复 原文
池木 2024-10-11 23:08:47

您必须从最后一列开始，检查元素的总和是否为 N-1，一旦找到总和 = N-1 的列，搜索包含 0 的列，这就是您要查找的列...

You have to start with the last column, and check if the sum of the element is N-1, once you have found the column with the sum = N-1 search the column containing a 0 and this is the one you are looking for...

回复 原文
江湖正好 2024-10-11 23:08:47

@codaddict 的优化版本

int best = N;
int answer = -1;

for(int i=0;i<N;i++)
   for(int j=0;j<best;j++) 
       if (arr[i][j] != 0) {
          best = j;
          answer = i;
        }

一旦确定该行不会比当前答案更好，内部循环就会停止。这可以减少对比迄今为止最佳答案更长的行的大量搜索。

An optimised version of @codaddict

int best = N;
int answer = -1;

for(int i=0;i<N;i++)
   for(int j=0;j<best;j++) 
       if (arr[i][j] != 0) {
          best = j;
          answer = i;
        }

The inner loops stops as soon as it determines this row won't be the better than the current answer. This could cut out alot of searching down rows which are longer than the best answer so far.

回复 原文
來不及說愛妳 2024-10-11 23:08:47

查找哪一行在最远的列中具有第一个非零值。如果它是二进制的，MSB 位于左侧，LSB 位于右侧，则答案是以最多 0 开头的行。

Find which row has the first non zero value in the furthest column. If it is binary, with the MSB on the left, and the LSB on the right the answer is the row that starts with the most zeros.

回复 原文
西瓜 2024-10-11 23:08:47

如果可以的话，我会将其添加为对杰里米答案的评论，因为他的解决方案大部分是正确的。另外，我喜欢这种方法。在许多情况下，它会比其他答案快得多。有一个可能的问题。如果“每一行都已排序”。并不意味着所有的都向右移动，而是有一些其他含义（我可以想到几个含义。我需要提出问题的人提供更多信息）。一个问题...0011 和 0010 怎么样。行已排序可能意味着您正在实现的算法已被使用。他的答案中指定的算法无法区分两者。我会将两个答案的索引存储在一个数组中。如果数组长度为 1 那么你就有了一个解决方案，否则你需要进一步递归......只是一个想法。如果有人阅读本文并可以在其他帖子上发表评论，请在对其帖子的评论中引用此内容。这是一个严重的问题，如果技术上不正确的答案得到检查，那将是令人不安的。如果添加我的评论，我将完全删除我的答案。

I would add this as a comment to Jeremy's answer if i could, because his solution is mostly correct. Also, I like the approach. In many instances it will be MUCH faster than other answers. There is a possible problem. If "Each row is sorted." does not mean that all ones are shifted to the right, but has some other implication(I can think of a couple of implications. I would need more from the individual asking the question). One problem...what about 0011 and 0010. Rows are sorted could mean that the algorithm you are implementing is already used. The algorithm specified in his answer cannot distinguish between the two. I would store the index of both answers in an array. If array length is 1 then you have a solution, otherwise you need to recurse further...just a thought. If anyone reads this that can post comments on others posts please reference this in a comment to his post. It is a serious problem, and it would be upsetting to have a technically incorrect answer get the check. If my comment is added I will delete my answer completely.

回复 原文
花桑 2024-10-11 23:08:47

最小的数字可以是 0（类似于 (0000...0000)）或 1（类似于（0000...0001））。

每个较大的数字都类似于 (xxxx...xx11)。因此，您应该检查每一行的倒数第二个数字。如果是0则检查最后一位是否为0，如果是则为最小的数。如果没有，则记住行号并继续查找倒数第二个数字为 0 的行。如果找到的话，这将是最小的数字。如果不是，则第一个找到的数字是最小的数字。

这是具有 N+1 步骤（最坏情况）的解决方案，复杂度为 O(N)。

The smallest number can be 0 which looks like (0000...0000) or 1 which looks like (0000...0001).

Every larger number looks like (xxxx...xx11). So you should check the next to last digit in every row. If it is 0 then check if the last digit is 0. If it is it is the smallest number. If not, then remember the row number and continue looking for row with 0 on the next to last digit. If you find it, this will be the smallest number. If not, the first found number is smallest one.

This is the solution with N+1 steps (worst case scenario) which is O(N) complexity.

回复 原文
如此安好 2024-10-11 23:08:47

我不知道它是否被承认，但如果它已排序，您是否只需将每一行转换为十进制数字并选择具有较低行的行。
示例：

[0111] -> 7
[0011] -> 3
[0000] -> 0
[0001] -> 1

解决方案是值为 0 的行。或者？

I don't know if it's admitted, but if it's sorted don't you need just to convert each row to decimal number and choose the row with the lower one.
example:

[0111] -> 7
[0011] -> 3
[0000] -> 0
[0001] -> 1

The solution is the row with value 0. OR?

回复 原文
坠似风落 2024-10-11 23:08:47

我写了一个 O(n) 算法，类似于上面所说的，我们从左上角开始向下工作：

a = [
        [0, 1, 1, 1],
        [0, 0, 0, 1],
        [0, 0, 0, 0],
        [1, 1, 1, 1]
    ]
a2 = [
        [0, 0, 0, 0],
        [0, 1, 1, 1],
        [0, 0, 0, 1],
        [1, 1, 1, 1]
    ]

def search(a):
    n = len(a)
    c = 0
    r = 0
    best_row = 0
    while c<n and r<n:
        if a[r][c] == 0:
            c += 1
        else:
            best_row = r
            r += 1

    if c==n : best_row = r
    print( " best row: %d" % best_row )

search( a )
search( a2 )

I have written a O(n) algorithm, similar to what has been stated above, we start from top-left corner and work downwards:

a = [
        [0, 1, 1, 1],
        [0, 0, 0, 1],
        [0, 0, 0, 0],
        [1, 1, 1, 1]
    ]
a2 = [
        [0, 0, 0, 0],
        [0, 1, 1, 1],
        [0, 0, 0, 1],
        [1, 1, 1, 1]
    ]

def search(a):
    n = len(a)
    c = 0
    r = 0
    best_row = 0
    while c<n and r<n:
        if a[r][c] == 0:
            c += 1
        else:
            best_row = r
            r += 1

    if c==n : best_row = r
    print( " best row: %d" % best_row )

search( a )
search( a2 )
回复 原文
~没有更多了~

关于作者

你不是我要的菜∠

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

謌踐踏愛綪

文章 0 评论 0

开始看清了

文章 0 评论 0

高速公鹿

文章 0 评论 0

alipaysp_PLnULTzf66

文章 0 评论 0

热情消退

文章 0 评论 0

白色月光

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文