Напишите программу, которая сортирует массив и выводит все элементы массива, которые встречаются ровно 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_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .

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

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

@u235 5515 / 2868 / 571 Регистрация: 07.11.2019 Сообщений: 4,758
	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 5515 / 2868 / 571 Регистрация: 07.11.2019 Сообщений: 4,758
	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 раз

Решение