Как посчитать количество различных цифр в питоне

Условие

Дан список чисел. Определите, сколько в нем встречается различных чисел.

Примечание. Эту задачу на Питоне можно решить в одну строчку.

Решение

print(len(set(input().split())))

Комментарии

Виктор :

Не пойдет. Вы анализируете отдельные слова из входной строки как стринги, не как числа. Поэтому, например, числа, записанные как 7, 07 и 007, у вас будут посчитаны как три разных.

Добавить комментарий Отменить ответ

ЕГЭ на соточку для чайников

Прошу прощения, что так долго пропадал. Питошка вернулся, да еще и с группой в вконтакте, подписывайтесь. Помимо этого, на питошке откроется новая рубрика, в которой будут четкие объяснения всех заданий ЕГЭ и ОГЭ по информатике, внимательно прочитав которые, я уверен, вы улучшите свои баллы на экзамене ��

Количество разных чисел по модулю (оптимизация)

столкнулся вроде бы как с простой задачкой, но не получается уложиться в ограничение по памяти, заданное на сайте. Задан отсортированный массив целых чисел. Найдите количество различных по модулю чисел среди элементов массива. Входные данные: Первая строка содержит количество чисел n (n ≤ 2 * 10^6). Вторая строка содержит n целых чисел, отсортированных по возрастанию. Массив может содержать одинаковые элементы. Выходные данные: Выведите количество различных по модулю чисел. Пример : Входные данные:

9 -1 -1 -1 -1 0 1 1 1 1 

Выходные данные:

У меня два теста кушают 131 072 KiB, когда заданное ограничение — 128 MiB Есть подозрения, что нужно всё сделать через словари, но я не совсем понимаю, как это оформить. Ссылка на задание Вот мой код:

n = int(input()) lst_1 = [int(el) for el in input().split()] counter = 0 lst = set(lst_1) r = [] for i in lst: r.append(abs(i)) print(len(set(r))) 

Отслеживать
nikita sokolov
задан 12 ноя 2021 в 16:25
nikita sokolov nikita sokolov
99 6 6 бронзовых знаков
Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
12 ноя 2021 в 20:24

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

Задача оказалась про скорость ввода данных. Вот решение которое проходит все тесты (результаты):

import sys def read(): READ_SIZE = 1024 tail = '' while True: block = sys.stdin.read(READ_SIZE) if len(block) == 0: yield from tail.split() return text = tail + block last_ws = text.rfind(' ') if last_ws == -1: tail = text continue yield from text[:last_ws].split() tail = text[last_ws:] input() print(len(set(abs(int(w)) for w in read()))) 

Ограничения задачи — одна секунда, 128MB. Я сделал несколько тестов, чтобы понять как эти ограничения работают.

Прочитаем данные самым привычным для Питона способом:

input() print(len(input().split())) 

Результаты. То что это решение не решает задачу не важно. Меня интересует только память и время. Тесты 9 и 10 исчерпывают память полностью. На что расходуется память? На строку, которую вернул input() . На миллион (буквально) маленьких строчек, которые нарезал .split() и на список хранящий эти строки.

Главный вывод: каким бы ни был алгоритм обработки этого списка в дальнейшем, мы не помещаемся в память. Так читать данные нельзя.

А как можно? Единственное решение высокого уровня, которое читает слова из строки без создания длинного списка — re.finditer . Если вы знаете другие, подскажите.

import re input() print(sum(1 for _ in re.finditer('[0123456789]+', input()))) 

Результаты. Снова нас не интересует правильность, только память и время. На этот раз по памяти мы проходит свободно. Наибольшее потребление на девятом тесте — 24MB. Память расходуется на входную строку и миллион (буквально) объектов которые описывают найденные подстроки. Эти объекты не должны хранится, полагаю что сборщик мусора не успевает их убирать. Не суть.

Время работы этого варинта обескураживает: re.finditer тратит 412ms на восьмой тест, .split() — 146ms. re.finditer в 2.8 раза хуже.

Времени, которое остаётся после чтения данных re.finditer не хватает чтобы посчитать правильный ответ:

import re input() print(len(set(int(m.group(0)) for m in re.finditer('[0123456789]+', input())))) 

Результаты. Этот вариант даёт верные ответы, но не проходит по времени в тестах 9 и 10. Сколько времени нам не хватает? Восьмой тест в этом варианте — 840ms, в предыдущем — 412ms. Девятый тест в предыдущем — 758ms. Предполагая что обе программы имеют линейную сложность, получаем пропорцию для девятого теста на последнем коде: 758 / 412 * 840 = 1547ms . На полсекунды больше лимита по времени.

Напишем ввод руками. Функция read читает входной поток небольшими кусками, не хранит его целиком, выдаёт наружу как можно быстрее. Проверим как быстро читаются данные таким образом:

import sys def read(): READ_SIZE = 1024 tail = '' while True: block = sys.stdin.read(READ_SIZE) if len(block) == 0: yield from tail.split() return text = tail + block last_ws = text.rfind(' ') if last_ws == -1: tail = text continue yield from text[:last_ws].split() tail = text[last_ws:] input() print(sum(1 for _ in read())) 

Результаты. Девятый тест занимает 374ms. Аналогичное время для re.finditer — 758ms. Рукописное чтение обогнало библиотечное в два раза — неожиданный результат.

Сравним времена input().split() , re.finditer(. input()) и read() на тестах которые прошли по памяти для всех трёх вариантах:

вариант тест 7 тест 8 input().split() 125 146 read() 185 193 re.finditer(. input()) 395 412 

Самописный read() в полтора раза медленнее библиотечного input().split() , что подтверждает правило «чем выше уровень, тем быстрее код на Питоне». re.finditer разочаровал.

Для решения задачи пришлось идиоматичное но расточительное по памяти решение ( input().split() ) заменить менее быстрым но экономным рукописным ( read() ).

Как определить количество цифр в числе, не выделяя каждую отдельную цифру, с использованием str?

Сколько цифр в числе 1010, если оно записано в двоичной, десятичной, шестнадцатеричной?

SoreMix, это представление числа, а не само число. Представление числа 1010 в двоичной это 10, в десятичной это так и будет 1010, а в шестнадцатиричной это 4112. Речь о том что вопрос изначально некорректен. В какой системе счисления должно быть представлено число?

soremix @SoreMix Куратор тега Python

pfemidi, а разница какая? есть число, есть цифры из которого оно состоит. Никто не просил переводить в какие-то системы

SoreMix, так. По порядку. Если число, любое. Но если переменную, в которой хранится это число, перевести в его строковое представление, то количество цифр в этом строковом представлении будет разное для разных систем счисления, которое это строковое представление представляет.

Пример:
Дано число 65535.
В двоичном строковом представлении это 1111111111111111, то есть 16 цифр.
В восьмеричном строковом представлении это 177777, то есть 6 цифр.
В десятичном строковом представлении это 65535, то есть 5 цифр.
В шестнадцатиричном строковом представлении это FFFF, то есть 4 цифры.

Но внутри, в компьютере, оно как было 65535, так и всегда будет 65535.

Посчитать количество одинаковых элементов в списке

Дан список целых чисел. Посчитать, сколько раз в нем встречается каждое число. Например, если дан список [1, 1, 3, 2, 1, 3, 4], то в нем число 1 встречается три раза, число 3 — два раза, числа 2 и 4 — по одному разу.

Решение задачи на языке программирования Python

Для хранения количества каждого встречающегося в списке значения создадим словарь. В нем ключами будут числа, которые встречаются в списке, а значениями — количества этих чисел в списке. Для примера, приведенного выше, в итоге должна получиться такая структура: .

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

Другая функция будет считать количество каждого значения и заносить данные в словарь. Алгоритм подсчета заключается в следующем. Если очередной элемент списка уже есть в качестве ключа словаря, то следует увеличить значение этого ключа на единицу. Если очередного элемента списка нет в качестве ключа в словаре, то такой ключ следует добавить и присвоить ему значение, равное единице.

Для того, чтобы вывести содержимое словаря в отсортированном по возрастанию ключей виде, используется функция sorted . Она сортирует ключи словаря и помещает их в список.

from random import randint def fill_list(minimum, maximum, amount, empty_list): for i in range(amount): empty_list.append(randint(minimum, maximum)) def analysis(from_list, to_dict): for i in from_list: if i in to_dict: to_dict[i] += 1 else: to_dict[i] = 1 lst = [] dct = {} mn = int(input('Минимум: ')) mx = int(input('Максимум: ')) qty = int(input('Количество элементов: ')) fill_list(mn, mx, qty, lst) analysis(lst, dct) for item in sorted(dct): print(f"'': ") 

Минимум: 100 Максимум: 104 Количество элементов: 20 '100': 2 '101': 5 '102': 3 '103': 7 '104': 3

С другой стороны, если не требуется сохранять количества значений в программе, а надо только вывести их на экран (сохранить в файл, передать по сети), то задачу проще решить через использование спискового метода count() , который считает, сколько раз переданное в него значение встречается в списке, к которому применяется метод.

Если перебирать элементы самого списка, то метод count() будет вызываться несколько раз на одно и то же значение, если оно встречается в списке не единожды. Чтобы избежать этого, получим из списка множество и будем перебирать его элементы. Во множестве не бывает одинаковых значений.

from random import randint mn = int(input('Минимум: ')) mx = int(input('Максимум: ')) qty = int(input('Количество элементов: ')) lst = [randint(mn, mx) for i in range(qty)] s = set(lst) for i in s: print(f"'': ")

X Скрыть Наверх

Решение задач на Python