python - 在 O(n) 的排序矩阵中查找小于目标的 # 元素的算法？

Question

设计一个算法，输出 A 中小于或等于 x 的条目数。您的算法应该在 O(n) 时间内运行。

例如，在下面的数组中，如果我的目标是“5”，那么我将返回 2 b/c 1 和 3 较小。

[1, 3,  5]
[2, 6,  9]
[3, 6, 10]

我用下面的代码试了一下，它接近工作了，我认为它是 O(n) ... 我看到的问题是如果我的数组中没有 # 我不确定我是否返回正确的值吗？

def findLessX(m,n,x):
    i = 0
    j = n-1

    while (i < n and j >= 0):
        if i == n or j == n:
            print("n not found")
            return (i+1)*(j+1)-1


        if (m[i][j] == x):
            print(" n Found at ", i , " ", j)
            return (i+1)*(j+1)-1
        elif (m[i][j] > x):
            print(" Moving left one column")
            j = j - 1
        elif (m[i][j] < x):
            print(" Moving down one row")
            i = i + 1

    print(" n Element not found so return max")
    return (i)*(j+1)

# Driver code
x = 5
n = 3
m = [ [1, 3, 5],
      [2, 6, 9],
      [3, 6, 9]]
print("Count=", findLessX(m, n, x))

检查上面的计数和简单矩阵，看看 soln 是否有效~

Answer 1

如果列和行都按升序排序，那么对于任何给定的边框值，确实存在一些阶梯线。它将矩阵分为两部分 - 高于(等于)和低于边界值。该线总是向左和向下(如果遍历从右上角开始)。

[1, 3,  |5]
    ____|
[2,| 6,  9]
[3,| 6, 10]

因此从右上角开始扫描，在右侧或顶部边缘找到该行的起始单元格，然后沿着该行，计算留给它的元素。

复杂性是线性的，因为线永远不会回头。

附言我希望你能根据给定的线索编写代码

def countLessX(m,n,x):
    col = n-1
    count  = 0

    for row in range(n):
        while (col >= 0) and (m[row] [col] >= x):
            col = col - 1
        count = count + col + 1
    if col < 0:   #early stop for loop
        break
    return count

# Driver code
n = 3
m = [ [1, 3, 5],
      [2, 6, 9],
      [3, 6, 9]]
for x in range(11):
   print("x=", x, "Count=", countLessX(m, n, x))

x= 0 Count= 0
x= 1 Count= 0
x= 2 Count= 1
x= 3 Count= 2
x= 4 Count= 4
x= 5 Count= 4
x= 6 Count= 5
x= 7 Count= 7
x= 8 Count= 7
x= 9 Count= 7
x= 10 Count= 9