Найти середину списка
Это всего лишь пример функции, которая сможет найти середину любого списка. Это то, что вы можете сделать, используя понимание списка?
Изменить: это отличается от удаления средней точки, потому что я хотел бы просто распечатать среднее значение, если список нечетный, я хотел бы вернуть оба средних значения, как принятый ответ. Не получить медиану, как задал другой вопрос, и получить среднее из двух значений.
4 ответа
Зачем вам использовать понимание списка? Понимание списка знает только о любом члене списка за раз, так что это был бы странный подход. Вместо:
def findMiddle(input_list): middle = float(len(input_list))/2 if middle % 2 != 0: return input_list[int(middle - .5)] else: return (input_list[int(middle)], input_list[int(middle-1)]) Этот должен возвращать средний элемент в списке, если это список нечетных чисел, или кортеж, содержащий два средних элемента, если это список с четным номером.
Подумайте еще о том, как можно сделать это с помощью понимания списка, просто для удовольствия. Придумали это:
[lis[i] for i in range((len(lis)/2) - (1 if float(len(lis)) % 2 == 0 else 0), len(lis)/2+1)] «Вернуть массив, содержащий i th цифра (ы) массива lis где я есть / являются членами диапазона, который начинается в the length of lis, divided by 2, from which we then subtract either 1 if the length of the list is even, or 0 if it is odd и который заканчивается в the length of lis, divided by 2, to which we add 1 «.
Начало / конец диапазона соответствуют индексу (ам), из которых мы хотим извлечь lis учитывая, какие аргументы являются включающими / исключающими из range() функция в питоне.
Если вы знаете, что каждый раз это будет нечетный список длины, вы можете [0] до конца, чтобы получить фактическое единственное значение (вместо массива, содержащего единственное значение), но если это может или будет список четной длины, и вы хотите вернуть массив, содержащий два средних значения ИЛИ массив из одно значение, оставить как есть.:)
Найти середину массива питон
В таких языках, как C и Java, требуется заранее указывать размер массива и тип данных. Структура списка в Python позволяет обойти эти требования, сохраняя данные в виде указателей на местоположение элементов в памяти, автоматически изменяя размер массива, когда место заканчивается. Элементам памяти не обязательно находиться рядом друг с другом.
Реализация
Основные ограничения, с которыми мы сталкиваемся при создании массивов на языке Python:
- После выделения места для массива мы не можем получить больше, не создав новый массив.
- Все значения в массиве должны быть одного типа.
Мы можем реализовать в Python очень простой класс Array, который имитирует основную функциональность массивов в языках более низкого уровня.
Отсутствие ограничений на типы данных и длину делает связанные списки привлекательными. Однако эта гибкость создает некоторые проблемы. Программе доступен только верх списка, а это значит, что для поиска любого другого узла нам придется пройти весь список. Другими словами, мы лишаемся O(1) поиска для любого элемента, кроме первого узла. Если вы запрашиваете 100-й элемент, то для его получения потребуется 100 шагов: схема O(n).
Можно сделать связанные списки более универсальными. Для этого необходимо добавить указатели на предыдущие узлы и раскрыть конец списка, или сделать его кольцевым. В целом, выбор связанных списков вместо массивов является платой за удобство.
Реализация
Чтобы создать связанный список в Python, начнем с определения узла. Необходимы только две части: данные, которые хранит узел и указатель на следующий узел в списке. Добавим метод __repr__ для того, чтобы было легче увидеть содержание узла.
LC 141. Linked List Cycle: Цикл связанного списка – пример использования медленных и быстрых указателей. Наша цель определить, есть ли в списке цикл, который возникает, когда следующий указатель узла показывает на более ранний узел в списке.
Проблема в том, что проход списка через цикл будет бесконечным.
Один из вариантов решения заключается в том, что нам нужно установить ограничение на продолжительность выполнения обхода, или решить проблему повторяющихся паттернов за некоторый период времени.
Более простой подход заключается в использовании двух указателей.
В данном случае невозможно использование while fast и fast.next , так как эти методы имеют значение False только при достижении конца списка. Вместо этого, подставим slow и fast на первый и второй узлы. Будем перемещать их по списку с разной скоростью, пока они не совпадут. В конце списка вернем False . Если два указателя будут показывать на один и тот же узел, вернем True.
def has_cycle(head: ListNode) -> bool: """ Определяем где связанный список имеет цикл """ slow = head fast = head.next while slow != fast: # Находим конец списка if not (fast or fast.next): return False slow = slow.next fast = fast.next.next return True Мы узнали, что такое массивы и связанные списки. Это важная составляющая структур данных, которая используется во всех языках программирования.
В следующей части материала приступим к изучению деревьев и графов.