Есть ли дубликат числа в массиве

@Artem Baltysky · 23.09.2020, 07:24

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

Duplicates

У вас есть массив чисел длиною "N". Нужно найти есть ли дупликат в массиве?

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

(1 ≤ n ≤ 10000), где каждый элемент в массиве в промежутке (-10000 ≤ a[i] ≤ 10000)

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

Есть ли дупликат в массиве? "YES", "NO"

Пример 1
Ввод:
10
37 42 39 43 71 63 2 43 3 36

Вывод:
YES

@Catstail · 23.09.2020, 07:36

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def check_dup(arr):
    n=len(arr)
    for i in range(n-1):
        for j in range(i+1,n):
            if arr[i]==arr[j]:
                return True
    return False
  
z=[37,42, 39, 43, 71, 63, 2, 43, 3, 36]
 
if check_dup(z):
    print("YES")
else:
    print("NO")

Ввод списка сделай сам

@eaa · 23.09.2020, 08:09

Сейчас еще скажет, что по времени не проходит))

@Vigi · 23.09.2020, 08:18

Python
1
2
3
4
n = input() # только для систем проверок :)
arr = [i for i in input().split()]
tmp = list(set(arr))
print('YES' if tmp != arr else 'NO')

@Garry Galler · 23.09.2020, 19:36

Vigi,
Нужно len проверять, а не равенство самих списков. Иначе одинаковые по данным списки будут неодинаковы по порядку (set выдает отсортированный (частично или полностью) по возрастанию набор).

Python
1
2
def check_dup(arr):
    return len(set(arr)) != len(arr)

Вариант с set в любом случае быстрее для наихудших случаев: один дубликат в конце списка или отсутствие дубликатов.
Вариант Catstail, будет быстрее для наилучших случаев: первый дубликат располагается как можно ближе к началу. Для наихудших случаев лучше даже не пробовать.
У меня он не закончил работу до сих пор на миллионном списке с дубликатом в конце, хотя set выдал результат за 351 ms.
Средний по сложности вариант: сортировка и сравнение соседей за один проход (будет работать в 2-3 раза медленнее set для наихудших случаев.)

Новые блоги и статьи Все статьи Все блоги /
попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .
Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .