Массив: Найдите количество различных по модулю чисел среди элементов массива

@BITTIX · Регистрация: 04.03.2018

Студворк — интернет-сервис помощи студентам

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

Выходные данные
Выведите количество различных по модулю чисел.

@eaa · 04.12.2019, 10:48

Что именно не получается?

@BITTIX · 04.12.2019, 11:01 **[ТС]**

Вот мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import math
k=input()
if len(k)==1:
    k=int(k)
    a=input()
    n1=a.split(' ')
    n = [int(n) for n in n1] 
    f=[]
    if k==len(n):
        for i in range(len(n)):
            f.append(n.count(math.fabs(n[i]))-1)
            for j in range(len(n)):
                if type(n)==int:
                    n[j]=''
        for i in f:
            k-=i
            
        print(k)

@dondublon · 04.12.2019, 11:12

BITTIX, налицо двойной цикл, плюс функция .count делает отдельный проход.

Поскольку массив отсортирован - одинаковые элементы находятся рядом. Можно посчитать количество таких "серий" через itertools.groupby. Если бы не был отсортирован - тогда через множество, set.

@eaa · 04.12.2019, 11:36

dondublon, тут алгоритм O(n). n <= 10⁶. Сложность list to set какая?

Сообщение от BITTIX

Найдите количество различных по модулю чисел

@dondublon · 04.12.2019, 12:18

eaa, сложность сложная. Но особых вариантов нет.
Тут либо писать свою вариацию на тему set, и вряд ли она получится лучше, чем встроенная. Либо воспользоваться тем, что наши элементы - это int-ы и делать счётчик через список. Годится для кучи небольших значений.

@eaa · 04.12.2019, 12:29

Сообщение от dondublon

Но особых вариантов нет

Как нет? Тут есть решение за O(n) без дополнительной памяти.
Merge two sorted list (слияние двух отсортированных списков) просто модифицировать и все.

@dondublon · 04.12.2019, 12:43

eaa, тут, как я уже отметил, множества не нужны, потому что список отсортирован, одинаковые значения рядом, используем просто itertools.groupby. O(n) без дополнительной памяти, ага. Множества были бы нужны, если бы он не был отсортирован.
К чему тут merge two sorted list - непонятно. Список, вроде как, один.

@eaa · 04.12.2019, 16:15

Сообщение от dondublon

используем просто itertools.groupby

Python
1
2
a = [-19, -15, -10, -7, -4, -3, -1, -1, 1, 3, 4, 7, 10, 11, 11, 13, 19, 19, 19, 20]
itertools.groupby(a, lambda x: abs(x))

По Вашему нужно сделать так? Отсортирован же, сгруппирует правильно?

@dondublon · 04.12.2019, 17:25

eaa, сорри, просмотрел.
Тогда уже придётся извращаться. В общем, с set-ом тоже будет быстро, но можно обойтись.

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@BITTIX 0 / 0 / 0 Регистрация: 04.03.2018 Сообщений: 24

	Массив: Найдите количество различных по модулю чисел среди элементов массива 04.12.2019, 09:42. Показов 4109. Ответов 9 Метки нет (Все метки) Задан отсортированный массив целых чисел. Найдите количество различных по модулю чисел среди элементов массива. Входные данные Первая строка содержит количество чисел n (n ≤ 2 * 106). Вторая строка содержит n целых чисел, отсортированных по возрастанию. Массив может содержать одинаковые элементы. Выходные данные Выведите количество различных по модулю чисел. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	04.12.2019, 10:48
	Что именно не получается? 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	04.12.2019, 11:12
	BITTIX, налицо двойной цикл, плюс функция .count делает отдельный проход. Поскольку массив отсортирован - одинаковые элементы находятся рядом. Можно посчитать количество таких "серий" через itertools.groupby. Если бы не был отсортирован - тогда через множество, set. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	04.12.2019, 12:18
	eaa, сложность сложная. Но особых вариантов нет. Тут либо писать свою вариацию на тему set, и вряд ли она получится лучше, чем встроенная. Либо воспользоваться тем, что наши элементы - это int-ы и делать счётчик через список. Годится для кучи небольших значений. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	04.12.2019, 12:43
	eaa, тут, как я уже отметил, множества не нужны, потому что список отсортирован, одинаковые значения рядом, используем просто itertools.groupby. O(n) без дополнительной памяти, ага. Множества были бы нужны, если бы он не был отсортирован. К чему тут merge two sorted list - непонятно. Список, вроде как, один. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	04.12.2019, 17:25
	eaa, сорри, просмотрел. Тогда уже придётся извращаться. В общем, с set-ом тоже будет быстро, но можно обойтись. 0