1

Тема: Вивід подвійних чисел

На вхід отримуємо список чисел наприклад:
1 1 1 1 1 2 4 2 3 9 8 3 2 8 1 6 5 8
на вихід маємо отримати числа, які повторюються більше 1 разу:
1 2 3 8
якщо на вхід попадає одне число не виводимо нічого

написав код:

a = [int(i) for i in input().split()]
a.sort()
d = len(a)-1
i = 0
if a[0] > d:
    print('')
while i < d:
    if a[i] == a[i+1]:
        print(a[i])
        i+=1
        while a[i] == a[i+1]:
            i+=1
    if a[i] != a[i+1]:
        i+=1

Код працює
Але не проходить тест, видає помилку:

ailed test #3 of 85. Runtime error

Traceback (most recent call last):
  File "jailed_code", line 11, in <module>
    while a[i] == a[i+1]:
IndexError: list index out of range

Допоможіть розібратись.
Завчасно Дякую.!!!

2

Re: Вивід подвійних чисел

нащо так складно?

data = "1 1 1 1 1 2 4 2 3 9 8 3 2 8 1 6 5 8".split()
res = set()
while len(data):
    i = data.pop()
    if i in data:
        res.add(i)

prine(res)
Подякували: GvBogdan1

3 Востаннє редагувалося koala (02.05.2020 18:41:18)

Re: Вивід подвійних чисел

GvBogdan написав:

Допоможіть розібратись.

Переробіть на

while i<d and a[i]==a[i+1]:
ping написав:

нащо так складно?

У топікстартера складність O(n*log(n)), а у вас - O(n**2). Не скажу, що в нього ідеальний код, але хоча б для цього.

Подякували: GvBogdan1

4

Re: Вивід подвійних чисел

ping написав:

нащо так складно?

data = "1 1 1 1 1 2 4 2 3 9 8 3 2 8 1 6 5 8".split()
res = set()
while len(data):
    i = data.pop()
    if i in data:
        res.add(i)

prine(res)

Дякую!
Просто ми ще не вчили цей метод.
Матиму на увазі!

5

Re: Вивід подвійних чисел

Якщо вже треба пітонічно, то

from collections import Counter
data = "1 1 1 1 1 2 4 2 3 9 8 3 2 8 1 6 5 8".split()
print(*(v for v,c in Counter(data).items() if c>=2))

А код пана ping не просто неефективний, а ще й модифікує дані. Не треба так робити.

Подякували: GvBogdan, ping, leofun013

6

Re: Вивід подвійних чисел

koala написав:
GvBogdan написав:

Допоможіть розібратись.

Переробіть на

while i<d and a[i]==a[i+1]:
ping написав:

нащо так складно?

У топікстартера складність O(n*log(n)), а у вас - O(n**2). Не скажу, що в нього ідеальний код, але хоча б для цього.

не погоджуюся

«Передчасна оптимізація - це корінь всіх бід» (с)

спершу пишемо зрозумілий і легкопідтримуваний код
якщо отримали проблему швидкодії - починаємо оптимізацію.

звісно, є випадок - з самого початку знаємо що мова іде про ДУЖЕ великий набір чисел - тоді  беремо спеціалізований інструмент для таких даних а не викручуємо алгоритми пітоном

наприклад:

import numpy as np

data = np.array([int(i) for i in "1 1 1 1 1 2 4 2 3 9 8 3 2 8 1 6 5 8".split()])
data, count = np.unique(data, return_counts=True)
print(data[count > 1])
Подякували: koala1

7

Re: Вивід подвійних чисел

koala написав:
GvBogdan написав:

Допоможіть розібратись.

Переробіть на

while i<d and a[i]==a[i+1]:
ping написав:

нащо так складно?

У топікстартера складність O(n*log(n)), а у вас - O(n**2). Не скажу, що в нього ідеальний код, але хоча б для цього.

Дякую за відповідь цей тест пройшла програма, але попалась на другому:

Failed test #3 of 85. Runtime error

Traceback (most recent call last):
  File "jailed_code", line 13, in <module>
    if a[i] != a[i + 1]:
IndexError: list index out of range

Якщо і тут додати цикл while
то дальше теж не піде

Failed test #6 of 85. Time limit exceeded

як це обійти?

8 Востаннє редагувалося koala (02.05.2020 19:35:07)

Re: Вивід подвійних чисел

Подумаємо.

d = len(a)-1
i = 0
if a[0] > d: #
    print('')  #a[0] - початковий елемент, d - кількість елементів. Нащо це треба?
while i < d:
    if a[i] == a[i+1]: #в цьому місці i точно в межах, а a[i] та a[i+1] можуть бути рівними чи ні
        print(a[i])
        i+=1 #i змінилося, тому i+1 могло вийти за межі, а a[i] та a[i+1] можуть бути рівними чи ні
        while i<d and a[i] == a[i+1]: #тому тут треба перевірити, чи i в межах
            i+=1 #i знову змінилося
    #якщо ми вийшли з циклу, то точно знаємо, що a[i]!=a[i+1] або i поза межами, а якщо не були в першій гілці, то точно значємо, що a[i]!=a[i+1]
    if a[i] != a[i+1]: #тобто ця умова завжди справджується, її можна прибрати і завжди додавати 1.
        i+=1
Подякували: GvBogdan1

9

Re: Вивід подвійних чисел

ось пітонічний без імпортів

data = "1 1 1 1 1 2 4 2 3 9 8 3 2 8 1 6 5 8".split()
res = set()
for i, v in enumerate(data[: -1]):
    if v in data[i + 1:]:
        res.add(v)
print((res)

або коротше

data = "1 1 1 1 1 2 4 2 3 9 8 3 2 8 1 6 5 8".split()
print({v for i, v in enumerate(data[: -1]) if v in data[i+1:]})
Подякували: koala, GvBogdan, leofun013

10

Re: Вивід подвійних чисел

koala написав:

Подумаємо.

d = len(a)-1
i = 0
if a[0] > d: #
    print('')  #a[0] - початковий елемент, d - кількість елементів. Нащо це треба?
while i < d:
    if a[i] == a[i+1]: #в цьому місці i точно в межах, а a[i] та a[i+1] можуть бути рівними чи ні
        print(a[i])
        i+=1 #i змінилося, тому i+1 могло вийти за межі, а a[i] та a[i+1] можуть бути рівними чи ні
        while i<d and a[i] == a[i+1]: #тому тут треба перевірити, чи i в межах
            i+=1 #i знову змінилося
    #якщо ми вийшли з циклу, то точно знаємо, що a[i]!=a[i+1] або i поза межами, а якщо не були в першій гілці, то точно значємо, що a[i]!=a[i+1]
    if a[i] != a[i+1]: #тобто ця умова завжди справджується, її можна прибрати і завжди додавати 1.
        i+=1

Дійсно це була зайва перевірка

if a[i] != a[i+1]:

Я Вам дуже Дякую!
Особливо за те, що гарно пояснили мені!
Я два дні голову ламав))

А тут перевірка, якщо дано одне число то нічого не виводимо. Так в умові задачі.

if a[0] > d: #
    print('')  #a[0] - початковий елемент, d - кількість елементів. Нащо це треба?

11

Re: Вивід подвійних чисел

koala написав:
GvBogdan написав:

Допоможіть розібратись.

Переробіть на

while i<d and a[i]==a[i+1]:
ping написав:

нащо так складно?

У топікстартера складність O(n*log(n)), а у вас - O(n**2). Не скажу, що в нього ідеальний код, але хоча б для цього.

А "О" це у вас тут як "О-велике" у матані?

12

Re: Вивід подвійних чисел

31414 написав:

А "О" це у вас тут як "О-велике" у матані?

Не "як", а воно і є.

13 Востаннє редагувалося 31414 (13.05.2020 14:07:51)

Re: Вивід подвійних чисел

koala написав:
31414 написав:

А "О" це у вас тут як "О-велике" у матані?

Не "як", а воно і є.

а як ви визначали складність?

14 Востаннє редагувалося koala (13.05.2020 14:45:43)

Re: Вивід подвійних чисел

Полічив кількість операцій :)
Якщо серйозно, то в першому алгоритмі все лінійне (вкладені цикли хай не плутають - вони збільшують одну змінну i, тобто алгоритм пройдеться по всіх елементах по одному разу), крім a.sort(). Стандартний sort зазвичай  O(n*log(n)) - звідси й оцінка.
У пана ping цикл по n елементах (множник n) і всередині вирізання (складність n) та пошук (операція in, складність n). В результаті - O(n*n)==O(n**2). Якщо моє пояснення незрозуміле, то трохи детальніше питайте.

Подякували: leofun011