java - 如何用更快的东西替换 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

这是如何仅使用数组而不是 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)));
    }
}

如果您有一个导致性能问题的有值(value)的示例，您可以使用并比较这两种解决方案或在此处发布，我可以尝试帮助您进行调整。