Найти единственное число в бинарном дереве
Есть некоторое бинарное дерево и каждый элемент в нем содержится дважды кроме одного. Его-то и нужно найти)
Требуется написать алгоритм поиска такого числа за логарифмическую сложность и при этом создавать новые массивы и коллекции нельзя. На вход подается корень дерева
Пример [2,2,1]-> 1,[4,1,2,1,2]-> 4,[1]-> 1
Ответы (1 шт):
Автор решения: Nowhere Man
→ Ссылка
У вас на входе неотсортированный массив, который ещё как-то следует преобразовать в бинарное дерево, и это преобразование вряд ли будет иметь логарифмическую сложность.
А найти единственный уникальный непарный элемент в массиве, где должны содержаться только пары можно с помощью операции XOR со сложностью O(N), просто "сложив" все элементы такого массива.
- Реализация с циклом:
public static int findUnique(int ... pairs) {
int result = pairs[0];
for (int i = 1; i < pairs.length; i++) {
result ^= pairs[i];
}
return result;
}
- Реализация с использованием
IntStream::reduce(Stream API)
public static int findUnique(int ... pairs) {
return Arrays.stream(pairs).reduce((x, y) -> x ^ y).getAsInt();
}