Самый быстрый способ исключить числа из массива в каждой итерации l oop - PullRequest
Новая
       12

Самый быстрый способ исключить числа из массива в каждой итерации l oop

0 голосов
/ 03 марта 2020

Я не эксперт python.

Я пытаюсь найти решение для проблемы интервала K-раскраски. Только с использованием стандартной библиотеки python, поэтому numpy,.

Чего я хочу достичь:

Итак, у меня есть отсортированный список элементов, и в каждой итерации l oop мне нужно исключить несколько элементов, так что на следующей итерации l oop продолжает работать с подмножеством sorted это произошло в результате последней итерации. На каждой итерации я обращаюсь к индексам, используя алгоритм двоичного поиска, и список всегда должен быть отсортирован при работе.

Я пытался использовать array.pop (index), но мое решение было медленным и неэффективным для список из 100000 элементов, поскольку он имеет сложность O (n) в соответствии с https://wiki.python.org/moin/TimeComplexity, где n - количество элементов в списке.

Я попытался сохранить входные данные в наборе () и работаем с ними, однако, поскольку на каждой итерации мне нужно выполнять алгоритм двоичного поиска, я не могу их сохранить, потому что мне потребуется доступ к элементам по индексу для двоичного поиска, что невозможно в наборе TypeError: 'set' object is not subscriptable.

Пример:

Входные данные - это список, отсортированный в порядке возрастания в соответствии со вторым элементом каждого подмассива. 

arr = [[0, -1, 0], [1, 4, 0], [3, 5, 0], [0, 6, 0], [4, 7, 0], [3, 7, 0], [5, 9, 0], [6, 10, 0]]

for i in range(len(arr)) :

   x = binarysearch(arr, value) #returns an index

   while x > 0 :
      helper = x
      array.exclude(x)
      x = binarysearch(arr, arr[helper][0]) #returns an index

Я не хочу, чтобы все обр [x] , которые были исключены из последней итерации для включения в текущую.

Любые идеи мыслей будут высоко оценены.

Заранее спасибо

...