найти самое делимое число в массиве?

Question

Есть вопрос в интервью, найти наиболее делимые на другие числа в массиве, скажем, [2,4,8], 8 можно разделить на 3 числа, и это ответ.У меня есть решение O (N ^ 2), но есть ли лучшее решение, чем O (N ^ 2)?

Я думаю, что-то вроде быстрой сортировки будет иметь смысл, но пока не получит решение, какесли a% b, b% c => a% c, но операция% не является переходной, как> операция.

Answer 1

Вы можете работать с деревьями с помощью O (NlogN).

Самый быстрый алгоритм, который я считаю, состоит в создании кучи (дерево AVL - лучший выбор) с этим правилом:

Дляinput x: find x% node [i] == 0 или node [i]% x == 0

Если вы нашли этот узел, добавьте x в дочернюю коллекцию узла [i] или замените Node [i] с помощью x и добавьте узел [i] в ​​коллекцию детей x.

иначе добавьте этот узел в корневой узел.