需要帮助计算序列的元素

Question

我写了一个算法，应该计算一个序列的第 n 个元素，直到 n = 2000000。这个序列如下：

1 - 第一个元素是1；

2 - 对于序列的每个元素x，序列中也包含元素2x+1和3x+1；

3 - 每个元素都是升序排列，没有重复的元素；

4 - 该序列没有其他值；

使得前几个元素为[1, 3, 4, 7, 9, 10, 13, 15...], seq(50) = 175, seq(50000) = 1237222, seq(1234567 ) = 71221051等

我写了下面的代码：

public static long seq(int n) {
    LinkedList<Long> sequence = new LinkedList<>();
    int doubleCount = 0;
    int tripleCount = 0;
    long elementDouble = 1;
    long elementTriple = 0;
    sequence.addLast(elementDouble);
    while (sequence.size() <= n + 2) {
        elementDouble = 2 * sequence.get(doubleCount) + 1; 
        elementTriple = 3 * sequence.get(tripleCount) + 1;
        if (elementDouble < elementTriple && elementDouble > sequence.getLast()) {
            sequence.addLast(elementDouble);
            doubleCount++;
        } else if (elementDouble == sequence.getLast()) {
            doubleCount++;
        } else if (elementTriple > sequence.getLast()) {
            sequence.addLast(elementTriple);
            tripleCount++;
        } else {
            tripleCount++;
        }
    }
    return sequence.get(n);
}

分别计算 2x + 1 和 3x + 1 ，以便将两个值中的最小值添加到列表中，另一个值存储并与下一个对应值进行比较。这给了我正确的结果。但是，对于大于 1000000 的 n 值，它会非常慢（运行时间超过 5 分钟）。有什么方法可以改进代码，以便我可以将它用于 n 的极大实例吗？

非常感谢您的帮助:)

Answer 1

您可以尝试维护两个单独的队列，q1 和 q2。使1成为序列的第一个元素，然后将2*1 + 1 == 3入队q1，3*1 + 1 == 4入队q2。序列的下一个元素是每个队列前面两个元素中较小的一个。将其出列并调用它 x。序列的下一个元素是 x，您可以在 q1 中排队 2*x + 1，在 q2 中排队 3*x + 1。

Answer 2

您的代码执行得非常糟糕，因为您在 LinkedList 上调用 get(index)。改为使用 ArrayList 将大大提高性能：

public static long seq(int n) {
    ArrayList<Long> sequence = new ArrayList<>();
    int doubleCount = 0;
    int tripleCount = 0;
    long elementDouble = 1;
    long elementTriple = 0;
    sequence.add(elementDouble);
    while (sequence.size() <= n + 2) {
        elementDouble = 2 * sequence.get(doubleCount) + 1; 
        elementTriple = 3 * sequence.get(tripleCount) + 1;
        if (elementDouble < elementTriple && elementDouble > sequence.get(sequence.size() - 1)) {
            sequence.add(elementDouble);
            doubleCount++;
        } else if (elementDouble == sequence.get(sequence.size() - 1)) {
            doubleCount++;
        } else if (elementTriple > sequence.get(sequence.size() - 1)) {
            sequence.add(elementTriple);
            tripleCount++;
        } else {
            tripleCount++;
        }
    }
    return sequence.get(n);
}

测试

public static void main(String[] args) {
    test(50);
    test(50000);
    test(1000000);
    test(1234567);
    test(10000000);
    test(100000000);
}
static void test(int n) {
    long start = System.nanoTime();
    long seq = seq(n);
    long end = System.nanoTime();
    System.out.printf("%d: %d (%.9fs)%n", n, seq, (end - start) / 1e9);
}

输出

50: 175 (0.000202500s)
50000: 1237222 (0.008792100s)
1000000: 54381286 (0.100169600s)
1234567: 71221051 (0.084787500s)
10000000: 1031926810 (0.454602800s)
100000000: 19115394879 (4.044839300s)

需要帮助计算序列的元素

Need help calculating the elements of a sequence

java

linked-list

sequence

time-complexity