Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

задачка

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

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

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

P.S. Есть разные способы решения (я нашёл один из них, но не лучший, как потом узнал). Если из алгоритма неочевидно, что он всегда работает, нужно это доказать, иначе решение неполное.
Subscribe
  • 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 →