Оптимизация пространственной сложности для задачи, связанной с подсчетом уникальных кратных 2 или более чисел?

Question

Пример ввода:

14
3
4
8

Мне просто нужно выяснить уникальные кратные 3 последних числа, вплоть до первого числа.Итак, уникальные кратные 3, 4 и 8 до 14, которые будут 3, 9, 12, 4, 8.

Решение, о котором я думаю, будет включать несколько структур данных, ипросто добавление и подсчет размера структур в конце или решение O (N ^ 2), которое включало бы итерацию по структуре при каждой потенциальной вставке, чтобы избежать повторений.

Не окажется ли решение, которое уменьшает сложность этой проблемы, более сложным, чем нужно?

Answer 1

Вы можете вычислить это быстро только с постоянным пробелом.

Учитывая LIMIT, A, B, C , ответ, который вы хотите, это число, кратное A , B и C , минус количество кратных каждой пары (потому что они были бы подсчитаны дважды), плюс количество кратных всех 3 (потому что это будет иметьбыл посчитан 3 раза, а затем вычтен 3 раза).

Где LCM (x, y, ...) - наименьшее общее кратное его аргументов, формула:

пол (LIMIT / A) + пол (LIMIT / B) + пол (LIMIT / C) - пол (LIMIT / LCM (A, B)) - пол (LIMIT / LCM (A, C))- этаж (LIMIT / LCM (B, C)) + этаж (LIMIT / LCM (A, B, C))

Для вашего примера это:

этаж(14/3) + пол (14/4) + пол (14/8) - пол (14/12) - пол (14/24) - пол (14/8) + пол (14/24)

= 4 + 3 + 1 - 1 - 0 - 1 + 0

= 6

Хмм ...у вас есть только 5 номеров в вашем списке для этого примера- номер 6 отсутствует.

Answer 2

Возможно, упоминание N было бы полезно, независимо от того,

пусть будет k чисел;a [0], a [1], ..., a [k-1]
и n - это максимальное число, кратное первому числу (L)

n = SUM(L/a[i]) ; i = 0, 1,..., k-1

Рассчитать и сложитькратные значения для массива / контейнера размером n
и Hashmap размера L могут использоваться для отслеживания дубликатов.

Сложность пространства будет O (L) и времясложность O (k * n)

Answer 3

Вы можете обойтись с O(n) пробелом и O(mlogn) сложностью времени (m - количество общих кратных), используя min-heap.Заполните кучу своими начальными числами с их текущим кратным числом (которое пока является просто самим числом) в качестве их ключа.Задайте для переменной last_seen переменную, которая будет меньше, чем ваше наименьшее начальное число (возможно, ноль).

Теперь удалите ключ min из кучи, если его значение больше last_seen и меньше или равно вашему.target_value распечатай.Затем установите last_seen равным этому ключу.Увеличьте значение ключа (представляющего текущий множитель) на значение начального числа, которое он сохранил (3 + 3 -> 6, 6 + 3 -> 9 и т. Д.), И снова добавьте его в min-heap.Повторяйте этот процесс, пока ключ min не станет больше target_value.Если в любой момент клавиша min равна last_seen, то это число является дубликатом - просто пропустите шаг печати и продолжайте как обычно.