Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

задачка

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

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

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

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

  • вот новый поворот

    В 1930-м году здание телефонной компании Белл в Индианаполисе, штат Индиана, было повернуто на 90 градусов в течение примерно месяца, чтобы…

  • о слугах и дверях

    seminarist недавно задал у себя в блоге отличный вопрос: "У ранней Агаты Кристи пару раз упоминается, что хороший дворецкий в…

  • навальный

    О происходящих в России событиях я редко пишу в последнее время, и по ряду причин это вряд ли сильно изменится, но сегодня я хочу отметить, что…

  • 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 →

  • вот новый поворот

    В 1930-м году здание телефонной компании Белл в Индианаполисе, штат Индиана, было повернуто на 90 градусов в течение примерно месяца, чтобы…

  • о слугах и дверях

    seminarist недавно задал у себя в блоге отличный вопрос: "У ранней Агаты Кристи пару раз упоминается, что хороший дворецкий в…

  • навальный

    О происходящих в России событиях я редко пишу в последнее время, и по ряду причин это вряд ли сильно изменится, но сегодня я хочу отметить, что…