Колян, ты знаешь решение или просто так обсуждаешь?

Решения за о(n) я не знаю

Денис же говорит что выше было много решений предложено.

Нет, второй цикл будет каждый раз выполнятся меньше чем чем в предыдущем проходе

Почитай про асимптотику

Получаешь арифметическую прогрессию

Где выходит квадратичнач функция с коэффициентом

Решения за о(n) я не знаю

Либо булев массив, либо хеш-таблица, в зависимости от ограничений

The best way would be to insert every element into a hash table (without sorting). This takes O(n) as constant time insertion. Then for every x, we can just look up its complement, T-x, which is O(1). Overall it takes will be O(n).

CONST = 42 number_to_look_for = set([]) for i in original_list: if i in number_to_look_for: return True if CONST - i in number_to_look_for: return True number_to_look_for.add(CONST - i)

Это же O(n) получается? Пропорциональна длине массива, проверка в set это O(1). По памяти максимум o(n)

The best way would be to insert every element into a hash table (without sorting). This takes O(n) as constant time insertion. Then for every x, we can just look up its complement, T-x, which is O(1). Overall it takes will be O(n).

Это откуда?

http://k2code.blogspot.in/2012/01/given-integer-array-and-number-x-find.html

http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number

CONST = 42 number_to_look_for = set([]) for i in original_list: if i in number_to_look_for: return True if CONST - i in number_to_look_for: return True number_to_look_for.add(CONST - i)

Обращение к сету - логарифм

смотря на чём сет делать)

Либо булев массив, либо хеш-таблица, в зависимости от ограничений

Булев массив это массив длины в диапазон инта?)

Уже начали что ли?

Нет ещё

а такое решение про 42 достаточно питонично? foo = lambda numbers: True if len([i for i in numbers if 42 - i in d]) and numbers.count(21)>1 else False

Сидим, ждем

/

Там же первый про ботов?

Можнл и опоздать)

Ага

дело не в питоничности а в сложности алгоритма

Я когда первое решение давал, сделал сет чтобы искать в нем бинарно, потом забыл сменить на дикт, так как сортировка не нужна

Лямбда вообще не питонично

В диапазон, который допустим в задаче

Я когда первое решение давал, сделал сет чтобы искать в нем бинарно, потом забыл сменить на дикт, так как сортировка не нужна

Ну, для каждого ты ищешь бинарно

Каждый * бинарно = nlogn

Как я понял - там либо O(n^2) либо расход по памяти. На практике если массив маленький - то пофиг на O(n^2), а если большой - то можно и в память упереться.

Как я понял - там либо O(n^2) либо расход по памяти. На практике если массив маленький - то пофиг на O(n^2), а если большой - то можно и в память упереться.

Можно n log без лишней памяти

Сорт + 2 указателя

Ну, для каждого ты ищешь бинарно

Нет, о1

Искать БИНАРНО

Я когда первое решение давал, сделал сет чтобы искать в нем бинарно, потом забыл сменить на дикт, так как сортировка не нужна

Поиск в хеше же, там коллизий для ин-тов не может быть

Мы бинарно за 0(1) ищем??

Поиск в хеше же, там коллизий для ин-тов не может быть

Может

Ага

А там есть кофеек?

Хз

Ничего не понятно про бинарного

:(

Бинарно

Я только воду

Ну если только > 2^64

Взял

а как задача вообще звучит?

Ну если только > 2^64

Нет, в качестве хеша берутся последние биты инта

Мы бинарно за 0(1) ищем??

Во втором примере вместо сета дикт булевый, я про это. Поиск офкоз логн

Тут в таком случае задача без ограничения по памяти становится

А там есть кофеек?

есть

И это чит

Обращение к сету - логарифм

Это хэш же, какой логарифм?

В условии нет про память

Об этом и говорю

Это хэш же, какой логарифм?

Положить туда логарифм

Об этом и говорю

Значит задача решена, дальше уже можно говорить про память

Положить туда логарифм

Тут пишут что O(1) https://wiki.python.org/moin/TimeComplexity

есть

Супер!

Нет, не пишут

Ты сам подумай, дерево представь

Как туда вставлять за о1 без сдвигов?

Это не дерево а хэш-таблица.

ERROR: S client not available

В питоне сет и дикт все делают за единицу

Она сортированная

Она сортированная

Нет

Жома протестирую

Вставка не должна быть о1

В сет

Ну оно правда не отсортированное, ни множество ни словарь. Для сортированности специально SortedDict придумали.

Ну оно правда не отсортированное, ни множество ни словарь. Для сортированности специально SortedDict придумали.

?

>>> set(('ab', 'ba', 'cd', 'dc')) {'ba', 'ab', 'cd', 'dc'}

Не отсортировано

Вставка не должна быть о1

Вставка - изменение одного поля в таблице

Ну меня переклинить что сортированное там по дереву, бывает :₽

Это в с++

Не отсортировано

set поможет удалить дубликаты

Значит можно не менять ничего чо

Кресты в питоночате

уж лучше хаскель

Жома протестирую

Тебе лучше не знать, что такое жом.

Вставка не должна быть о1

Ты про сет? Там не деревья, а хеш. С хорошей хеш функцией это О(1)

СортедДикт использует дополнительно список чтобы хранить порядок ключей

Python 3 PIL ругается на кириллицу при ImageDraw текста. Какие еще либы можно попробовать для вывода текста на картинку?

Побаловаться с encode

Заменить пил на PILLOW

Заменить пил на PILLOW

?

У меня все работает

Попробуем. Спасибо

(но лень выкапывать старый проект)

Удачи

Тебе лучше не знать, что такое жом.

Жома погуглю что такое жом

Да бля

Кто сделает заебали