0

Прохожу тест от Yandex и там дано задание

Дан массив a из n целых чисел. Напишите программу, которая найдет число, которое чаще других встречается в массиве.

Формат ввода В первой строке входных данных записано число n (1 ≤ n ≤ 300 000). Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 1 000 000 000).

Формат вывода Выведите единственное число x, наибольшее из чисел, которое чаще других встречается в массиве a.

>

Пример 1 

Ввод    Вывод 

3        3 
3 3 3 

Пример 2 
Ввод       Вывод 
5          4
4 1 4 3 3 


Пример 3 
Ввод                         Вывод 
10 
10 6 10 10 10 10 8 8 10 9     10

вот мой код :

def mostFrequent(a, b): 
  
    a.sort() 
  
    
    max_count = 1; res = a[0]; curr_count = 1
      
    for i in range(1, b):  
        if (a[i] == a[i - 1]): 
            curr_count += 1
              
        else : 
            if (curr_count > max_count):  
                max_count = curr_count 
                res = a[i - 1] 
              
            curr_count = 1
      
    # If last element is most frequent 
    if (curr_count > max_count): 
      
        max_count = curr_count 
        res = a[b - 1] 
      
    return res 
  
# Driver Code 
n = int(input())
a = [int(i) for i in input().split()]
b = len(a) 

print(mostFrequent(a, b))

и когда например я ввожу : n = 10 a = 10 10 10 10 50 50 50 50 То ответом выходит 50 , всё как в их задании , но всё время выдаёт ошибку " Неверный ответ " введите сюда описание изображения

P.S Тест успешно завалил.Но всё интересно где я ошибся и как они хотели получить ответ.

4

3 ответа 3

2

Попробуйте так (сложность алгоритма O(n)):

def parse_input(s):
    return list(map(int, s.split()))

def mode_max(items):
    max_val = -1
    max_count = -1
    d = {}
    for i in items:
        d[i] = d.get(i, 0) + 1
        if d[i] >= max_count:
            max_count = d[i]
            if i > max_val:
                 max_val = i                
    return max_val

тесты:

In [80]: mode_max(parse_input("10 6 10 10 10 10 8 8 10 9"))
Out[80]: 10

In [81]: mode_max(parse_input("10 10 10 10 50 50 50 50"))
Out[81]: 50
2
  • Не прошёл проверку и опять выдал ошибку : " ошибка в программе или неверный алгоритм" 4 июл 2019 в 20:01
  • из задачи В первой строке входных данных записано число n (1 ≤ n ≤ 300 000). Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 1 000 000 000). 4 июл 2019 в 20:02
1

Обратите внимание на это предложение в условии:

Выведите единственное число x, наибольшее из чисел, которое чаще других встречается в массиве a.

Если вы возьмёте второй пример из условия и введёте его в ваш код, то получите ответ 3. Но в примере ожидается ответ 4. В этом примере 3 и 4 встречаются одинаковое число раз (по два), но наибольшее из них - 4.

На вскидку кажется, что достаточно будет заменить в обоих условиях

if (curr_count > max_count):

знак "больше" на "больше или равно". Так как массив у вас отсортирован по возрастанию, то это гарантирует, что при равенстве счётчиков большее значение будет заменять меньшее. Сейчас же у вас наоборот - при равенстве счётчиков меньшее значение гарантированно сохранится.

1
  • Я исправил как Вы предложили , теперь когда я запускаю код то получаю значения как в примере , но всё равно не проходит код , не нравится всё так же алгоритм или сама программа 4 июл 2019 в 20:32
1

from collections import Counter
n = int(input()) 
a = [int(i) for i in input().split()]
c = Counter(a[0:n]).most_common()
max_inner = c[0][1]
c = [i[0] for i in c if i[1]==max_inner]
print(max(c))

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.