Как заменить SortedSet чем-то более быстрым или ускорить его

Question

Я пытаюсь решить проблему с LeetCode https://leetcode.com/problems/nth-magical-number/.Я могу представить свое решение, но я хотел бы ускорить его, я полагаю, один из способов сделать это - удалить использование коллекций

class Solution {
    private static final int MODULO = (int) (Math.pow(10, 9) + 7);

    private static int modulate(final long result) {
        return (int) (result % MODULO);
    }

    private static SortedSet<Integer> steps(final int smaller, final int larger) {
        final int lcm = lowestCommonMultiple(smaller, larger);
        final SortedSet<Integer> result = new TreeSet<>();
        final int max = lcm / smaller;
        final int min = lcm / larger;
        for (int i = 1; i <= max; i++) {
            result.add(i * smaller);
            if (i <= min) {
                result.add(i * larger);
            }
        }
        return result;
    }

    private static long nthNonZeroMagicalNumber(final int N, final int smaller, final int larger) {
        final SortedSet<Integer> stepsInCycle = steps(smaller, larger);
        final long lcm = stepsInCycle.last();
        final int inOneCycle = stepsInCycle.size();
        final int fullCycleCount = N / inOneCycle;
        int count = fullCycleCount * inOneCycle;
        final long evaluated = fullCycleCount * lcm;
        if (count == N) {
            return evaluated;
        }
        final int remainder = N - count - 1;
        return stepsInCycle.toArray(new Integer[stepsInCycle.size()])[remainder] + evaluated;
    }

    private static int greatestCommonDenominator(int a, int b) {
        while (b > 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private static int lowestCommonMultiple(final int a, final int b) {
         return a * (b / greatestCommonDenominator(a, b));
    }

    public static int nthMagicalNumber(final int N, final int A, final int B) {
        if (N == 0) {
            return 0;
        } else if (A == B) {
            final long result = (long) A * (long) N;
            return modulate(result);
        } else if (N == 1) {
            return modulate(Math.min(A, B));
        }
        return modulate(nthNonZeroMagicalNumber(N, Math.min(A, B), Math.max(A, B)));
    }
}

Я полагаю, что его можно заменить стандартным массивом.или что-то типа того.Заранее спасибо, ребята!

Answer 1

Вам не нужен набор или массивы для решения этой проблемы:

public static final long MAX_N = Double.valueOf(Math.pow(10.0, 9.0)).longValue();
public static final long MODULO_VALUE = MAX_N + 7L;

public static long nthMagicalNumber(long n, long a, long b) {
    long count = 0L;
    long sample = Math.min(a, b);
    long result = sample;

    do {
        result = sample;
        long nextA = ((sample / a) * a) + a;
        long nextB = ((sample / b) * b) + b;
        sample = Math.min(nextA, nextB);
        count++;
    } while(count < n);

    return result % MODULO_VALUE;
}

Answer 2

Это пример того, как делать только с массивом вместо SortedSet:

import java.util.Arrays;
import java.util.Objects;

class Solution {
    private static final int MODULO = (int) (Math.pow(10, 9) + 7);

    private static int modulate(final long result) {
        return (int) (result % MODULO);
    }

    private static Integer[] steps(final int smaller, final int larger) {
        final int lcm = lowestCommonMultiple(smaller, larger);
        final int max = lcm / smaller;
        final int min = lcm / larger;
        final Integer[] result = new Integer[max * 2];

        int pos = 0;
        for (int i = 1; i <= max; i++) {
            result[pos++] = (i * smaller);
            if (i <= min) {
                result[pos++] = (i * larger);
            }
        }
        return Arrays.stream(result)
                .filter(Objects::nonNull)
                .sorted()
                .distinct()
                .toArray(Integer[]::new);
    }

    private static long nthNonZeroMagicalNumber(final int N, final int smaller, final int larger) {
        final Integer[] stepsInCycle = steps(smaller, larger);
        final long lcm = stepsInCycle[stepsInCycle.length - 1];
        final int inOneCycle = stepsInCycle.length;
        final int fullCycleCount = N / inOneCycle;
        int count = fullCycleCount * inOneCycle;
        final long evaluated = fullCycleCount * lcm;
        if (count == N) {
            return evaluated;
        }
        final int remainder = N - count - 1;
        return stepsInCycle[remainder] + evaluated;
    }

    private static int greatestCommonDenominator(int a, int b) {
        while (b > 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private static int lowestCommonMultiple(final int a, final int b) {
        return a * (b / greatestCommonDenominator(a, b));
    }

    public static int nthMagicalNumber(final int N, final int A, final int B) {
        if (N == 0) {
            return 0;
        } else if (A == B) {
            final long result = (long) A * (long) N;
            return modulate(result);
        } else if (N == 1) {
            return modulate(Math.min(A, B));
        }
        return modulate(nthNonZeroMagicalNumber(N, Math.min(A, B), Math.max(A, B)));
    }
}

Если у вас есть пример значения, которое вызывает проблемы с производительностью, вы можете использовать и сравнить оба решения или опубликовать здесь, и я могу попытаться помочь в адаптации.