Поиск числа в отсортированном двумерном массиве

Question

Я пытаюсь найти номер, с которого я смотрю, в списке 2D-массивов.Тем не менее, его нужно сначала отсортировать перед поиском.

Кажется, все работает нормально, когда я пытаюсь найти число в двумерном массиве.Это просто факт сортировки двумерного массива так, что он все еще будет работать.Давайте предположим, что я хочу отсортировать массив 3х3 2D.Способ отображения:

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

Затем я буду искать число, используя метод двоичного поиска по отсортированному 2D-массиву.Мое среднее значение будет в середине массива из поиска.

Это всего лишь пример, но чего я хочу добиться, когда я ставлю случайные числа, а затем сортирую строки и столбцы.Используя эту идею, я использую библиотеку random.randint() из Python для рандомизации моих чисел.Затем я пытаюсь отсортировать потом в моем 2d массиве, но перед продолжением он не сортируется.

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)

Sorted:

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

Должен быть отсортированный 2D-массив.Возможно ли, чтобы строка и столбец сортировались соответственно с помощью отсортированной функции?

Answer 1

Наконец-то нашел правильное решение, не используя 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")

output:

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

Я хотел найти стандартный библиотечный модуль, где я мог быобъединить 2D массив в 1D и отсортировать его.Затем я хотел бы составить список моего 1D массива и встроить его в 2D массив.Это звучит много работ, но, кажется, работает хорошо.Дайте мне знать, если есть лучший способ сделать это без болтовни и быстрее:)

Answer 2

Вызов, отсортированный по вложенному списку, который будет сортироваться только по первому индексу в списке.

Пример:

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

вернется

[[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) возвращает число массивов, а (n) возвращает количество массивов.

Использование -1 в любом из параметров означает, что измененный массив будет пригоден для возврата требованийдругого параметра.

b вернется

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