Алгоритми та структури даних · Middle · Запитання 63 з 75
Кожне число в масиві трапляється двічі, крім одного. Як знайти його за O(n) часу й O(1) пам'яті?
- 1Порахувати входження кожного числа в хеш-таблиці
- ✓Правильна відповідь: XOR усіх чисел: пари взаємно знищуються, лишається одне
- 3Відсортувати масив і порівняти сусідні значення
Пояснення
a ^ a = 0 і a ^ 0 = a, а XOR комутативний, тож пари зникають у будь-якому порядку. Сортування - O(n log n); map - O(n) часу, але O(n) пам'яті.