Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

задачка

Хорошая программистская задачка:

Дан список с данными. И есть подозрение, что более половины элементов в списке - это один и тот же элемент (число, например). Требуется определить, так ли это, и если так — то что это за элемент и сколько раз он встречается. За линейное время и без дополнительной памяти. (кроме константы).

Ссылку на журнал, из которого взял, дам позже, т.к. в нём есть решение.

P.S. Есть разные способы решения (я нашёл один из них, но не лучший, как потом узнал). Если из алгоритма неочевидно, что он всегда работает, нужно это доказать, иначе решение неполное.
Subscribe

  • новые данные из израиля

    Минздрав Израиля выкатил новые данные с разбивкой больных и тяжелобольных по статусу вакцинации и возрастам. Вот сводная таблица, где все названия…

  • перечеркнуло все

    Илья Красильщик в ФБ: "С утра читал отзывы на электричку Москва–Рязань на сайте tutu.ru (реально рекомендую отзывы на электрички на сайте tutu.ru,…

  • принцессы не какают

    Тут израильский спортсмен Артем Долгопят взял золото на олимпиаде (вторая золотая медаль на Олимпиаде за всю историю Израиля), вся страна стоит на…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 86 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →

  • новые данные из израиля

    Минздрав Израиля выкатил новые данные с разбивкой больных и тяжелобольных по статусу вакцинации и возрастам. Вот сводная таблица, где все названия…

  • перечеркнуло все

    Илья Красильщик в ФБ: "С утра читал отзывы на электричку Москва–Рязань на сайте tutu.ru (реально рекомендую отзывы на электрички на сайте tutu.ru,…

  • принцессы не какают

    Тут израильский спортсмен Артем Долгопят взял золото на олимпиаде (вторая золотая медаль на Олимпиаде за всю историю Израиля), вся страна стоит на…