在排序的二维数组中搜索数字

Question

我试图在二维数组列表中找到我要查找的数字。但是，在搜索之前必须先排序。

当我尝试在二维数组中查找数字时，似乎一切正常。这只是以一种仍然有效的方式对二维数组进行排序的事实。假设我想对一个 3x3 二维数组进行排序。它应该显示的方式是：

    [[8, 27, 6],
     [1, 0, 11],
     [10, 9, 3]]

然后，我将使用二进制搜索方法在排序后的二维数组中查找数字。我的中间值将位于搜索数组的中间。

这只是一个示例，但是当我输入随机数然后对行和列进行排序时，我想要完成的事情。使用这个想法，我正在使用 Python 中的 random.randint() 库来随机化我的数字。然后，我试图在我的二维数组中进行排序，但在继续之前它并不是真正的排序。

n = 5
m = 5

def findnum_arr(array, num):
    low = 0
    high = n * m - 1
    while (high >= low):
        mid = (low + high) // 2
        i = mid // m
        j = mid % m

        if (num == array[i][j]):
            return True
        if (num < array[i][j]):
            high = mid - 1
        else:
            low = mid + 1
    return False

if __name__ == '__main__':
    multi_array = [[random.randint(0, 20) for x in range(n)] for y in range(m)]
    sorted(multi_array)

已排序：

    [[0, 1, 3],
     [6, 8, 9],
     [10, 11, 27]]

应该是排序后的二维数组。可否用sorted函数分别对行和列进行排序？

Answer 1

正在根据列表中的第一个索引进行排序的嵌套列表调用排序。

示例：

arr = [[8, 27, 6],[1, 0, 11],[10, 15, 3], [16, 12, 14], [4, 9, 13]]

即将 return

[[1, 0, 11], [4, 9, 13], [8, 27, 6], [10, 15, 3], [16, 12, 14]]

要按照您想要的方式执行此操作，您将不得不展平然后重塑。

为此，我会尝试引入 numpy。

import numpy as np


a = np.array(sorted(sum(arr, [])))

#sorted(sum(arr, [])) flattens the list

b = np.reshape(a, (-1,3)).tolist()

为清楚起见进行了编辑：您可以将 m 和 n 用作 np.reshape 中的参数。第一个参数 (m) 将 return 数组的数量，而 (n) 将 return 数组的数量。

在任一参数中使用 -1 意味着重塑后的数组将符合 return 另一个参数的要求。

b 会 return

[[0, 1, 3], [4, 6, 8], [9, 10, 11], [12, 13, 14], [15, 16, 27]]

Answer 2

终于在不使用 numpy 和避免 sum() 模块的情况下找到了合适的解决方案。

if __name__ == '__main__':
    x = 7
    multi_array = [[random.randint(0, 200) for x in range(n)] for y in range(m)]
    # one_array = sorted(list(itertools.chain.from_iterable(multi_array))) Another way if you are using itertools
    one_array = sorted([x for row in multi_array for x in row])
    sorted_2d = [one_array[i:i+m] for i in range(0, len(one_array), n)]

    print("multi_array list is: \n{0}\n".format(multi_array))
    print("sorted 2D array: \n{0}\n".format(sorted_2d))
    if not findnum_arr(sorted_2d, x):
        print("Not Found")
    else:
        print("Found")

输出：

multi_array list is:
[[40, 107, 23, 27, 42], [150, 84, 108, 191, 172], [154, 22, 161, 26, 31], [18, 150, 197, 77, 191], [96, 124, 81, 1
25, 186]]

sorted 2D array:
[[18, 22, 23, 26, 27], [31, 40, 42, 77, 81], [84, 96, 107, 108, 124], [125, 150, 150, 154, 161], [172, 186, 191, 1
91, 197]]

Not Found

我想找到一个标准库模块，我可以在其中将二维数组展平为一维数组并对其进行排序。然后，我会对我的一维数组进行列表理解并将其构建到二维数组中。这听起来很多工作，但似乎工作正常。让我知道是否有更好的方法可以不用 numpy 并且更快 :)

在排序的二维数组中搜索数字

Search a number in a sorted 2D array

python

sorting

search

2d

python-3.x