Напишите программу, которая сортирует массив и выводит все элементы массива, которые встречаются ровно K раз

@Xeib9 · Регистрация: 11.04.2020

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

Напишите программу, которая сортирует массив и выводит все элементы массива, которые встречаются ровно K раз.

Входные данные:
Первая строка содержит размер массива N . Во второй строке через пробел задаются N чисел – элементы массива. Гарантируется, что 0 < N ≤ 1000 . В третьей строке записано натуральное число K .

Выходные данные
Программа должна вывести все элементы массива, которые встречаются ровно K раз, в порядке возрастания, разделив их пробелами. Если таких элементов нет, программа должна вывести число 0.

Примеры
Входные данные
6
1 2 1 2 1 3
2

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

Заранее -- огромное спасибо.

@DmitryOST · 11.04.2020, 20:03

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n=int(input())
a = input()
a = a.split()
k = int(input())
h=0
s=1
r=[]
for i in range(n-1):
    h+=1
    for j in range(n-h):
        if a[i]==a[j+h]:
            s+=1
    if s==k and a[i] not in r:
        r.append(a[i])
        s=1
print(r)

Jabbson · 11.04.2020, 20:13

Python
1
2
3
4
n = int(input())
a = list(map(int, input().split()))
k = int(input())
print(*(sorted(x for x in set(a) if a.count(x) == k) or [0]))

@u235 · 11.04.2020, 20:16

Ввод массива, n,k - сделаете самостоятельно.

Python
1
2
3
4
a=[1, 2, 1, 2, 1,3, 3]
k=2
ans=sorted([i for i in set(a) if a.count(i)==k])
print(*ans)

Добавлено через 36 секунд
Jabbson, опередил.

Jabbson · 11.04.2020, 20:17

Python
1
2
3
4
n = int(input())
a = list(map(int, input().split()))
k = int(input())
print(*(sorted(x for x in set(a) if a.count(x) == k) or [0]))

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

Jabbson, опередил.

а как же

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

Если таких элементов нет, программа должна вывести число 0.

@u235 · 11.04.2020, 20:36

А это уже моя невнимательность при чтении условий задачи.

Jabbson · 11.04.2020, 20:38

там еще сортировать массив нужно было, но я не уверен с какой целью (наверное, чтобы искать повторения было "проще").

@u235 · 11.04.2020, 20:42

Не по теме:

Да, действительно, но на результат это не влияет. Что сортировать исходный массив, что выходной

Jabbson · 11.04.2020, 20:44

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

Сортировку я не забыл.

Я полагаю, имелась ввиду сортировка изначального массива.

@eaa · 11.04.2020, 23:04

сортировка O(n*logn), дальше groupby для подсчета ответа за O(n).
А count это O(n^2) - "квадрат".
Все просто!

Jabbson · 11.04.2020, 23:16

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

Все просто!

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

Добавлено через 1 минуту

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

А count это O(n^2) - "квадрат".

почему квадрат? не достаточно просто один раз пройти по всему листу?

@Garry Galler · 11.04.2020, 23:21

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

сортировать массив нужно было, но я не уверен с какой целью

Это чтобы поиск был быстрым.

Ваш вариант:

Python
1
2
def counting2(arr,k):
    return sorted(x for x in set(arr) if arr.count(x) == k) or [0]

Python
1
arr = [random.randint(1,1000) for i in range(1000)]

Code
1
2
%timeit -n 10 -r 10 counting2(arr,6)
23.5 ms ± 331 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)

C помощью сортировки подсчетом ровно за два цикла:

Python
1
2
3
4
5
6
7
8
9
10
11
12
def counting(arr, k):    
    max_elem = max(arr) + 1
    count = [0] * max_elem
      
    for element in arr:
        count[element] += 1
     
    result = []
    for element in set(arr):
        if count[element] == k:
            result.append(element)
    return result or [0]

Code
1
2
%timeit -n 10 -r 10 counting(arr,6)
345 µs ± 14.6 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)

Это потому что у варианта с count квадратичная сложность :-)

Почему здесь разумно применить сортировку подсчетом? Потому что условие "Гарантируется, что 0 < N ≤ 1000"
0..1000 - небольшой диапазон. Совсем немного памяти, но в 100 раз быстрее.

Jabbson · 11.04.2020, 23:31

Сообщение от Garry Galler

Потому что условие "Гарантируется, что 0 < N ≤ 1000"

а может это гарантируется, чтобы таким образом сказать - "там всего 1000 элементов, не парьтесь и пользуйтесь count"

@Garry Galler · 11.04.2020, 23:33

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

чтобы таким образом сказать - "там всего 1000 элементов, не парьтесь и пользуйтесь count"

Вряд ли. Обычно программы с count не проходят тестов по времени выполнения.
Но тут могут быть еще и ограничения по памяти. Тогда и мой вариант может не пройти.

@eaa · 11.04.2020, 23:37

Не по теме:

Garry Galler, действительно некоторые думают что count "бесплатный", как Вы высказались в одном из обсуждений.

@u235 · 12.04.2020, 17:59

del

@eaa · 12.04.2020, 18:04

сам count подсчет за O(n), если count в фильтре применять то получим O(n^2)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .

@Xeib9 0 / 0 / 0 Регистрация: 11.04.2020 Сообщений: 8

	Напишите программу, которая сортирует массив и выводит все элементы массива, которые встречаются ровно K раз 11.04.2020, 19:34. Показов 24871. Ответов 16 Метки python 3.x, сортировка (Все метки) Напишите программу, которая сортирует массив и выводит все элементы массива, которые встречаются ровно K раз. Входные данные: Первая строка содержит размер массива N . Во второй строке через пробел задаются N чисел – элементы массива. Гарантируется, что 0 < N ≤ 1000 . В третьей строке записано натуральное число K . Выходные данные Программа должна вывести все элементы массива, которые встречаются ровно K раз, в порядке возрастания, разделив их пробелами. Если таких элементов нет, программа должна вывести число 0. Примеры Входные данные 6 1 2 1 2 1 3 2 Выходные данные 2 Заранее -- огромное спасибо. 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,759
	11.04.2020, 20:36
	А это уже моя невнимательность при чтении условий задачи. 0

Jabbson 5907 / 3359 / 1036 Регистрация: 03.11.2009 Сообщений: 10,008
	11.04.2020, 20:38
	там еще сортировать массив нужно было, но я не уверен с какой целью (наверное, чтобы искать повторения было "проще"). 0

@u235
	11.04.2020, 20:42
	Не по теме: Да, действительно, но на результат это не влияет. Что сортировать исходный массив, что выходной 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	11.04.2020, 23:04
	сортировка O(n*logn), дальше groupby для подсчета ответа за O(n). А count это O(n^2) - "квадрат". Все просто! 0

@eaa
	11.04.2020, 23:37
	Не по теме: Garry Galler, действительно некоторые думают что count "бесплатный", как Вы высказались в одном из обсуждений. 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,759
	12.04.2020, 17:59
	del 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	12.04.2020, 18:04
	сам count подсчет за O(n), если count в фильтре применять то получим O(n^2) 1

Напишите программу, которая сортирует массив и выводит все элементы массива, которые встречаются ровно K раз

Решение