arrays - 从由任意两个或多个连续自然数相乘形成的排序数组中查找第 N 个数字

Question

我最近遇到了这个问题:

There is a (increasingly) sorted array formed by multiplying any two or more consecutive natural numbers.

2, 6, 12, 20, 24, 30, 42, 56, 60, 72 ...

Ex. 2 is formed by two consecutive natural numbers 1 and 2: 2 = 1×2. And 6 = 2×3 OR 1×2×3, 20 = 4×5.

If n is given as a parameter, find the nth number from the above array and return.

Limitation

• 1 ≤ n ≤ 1000000
• n is given only when the answer is smaller than 10¹²

所以在这里我能够找到 O(n2) 解决方案，但我想知道是否有更好的解决方案。
我的 O(n2) JS 解决方案:

function solution(n) {
    // Find all possible product subsets of [1, ..., n] = [1x2, 2x3, 4x5, ..., 1x2x...xn]
    // return Nth index of this product subset array

    // 1 ~ n+1 array
    const nums = Array.from({ length: n+1 }, (_, i) => i + 1);
    const set = new Set();

    // Find all possible product subsets
    for (let i = 0; i < nums.length; i++) {
        let accu = 1;
        for (let j = i; j < nums.length; j++) {
            accu *= nums[j];
            if (i !== j) set.add(accu);
        }
    }

    // Sort and return n-1 index value
    return Array.from(set).sort((a,b) => a - b)[n-1];
}

谢谢您的帮助 :)

Answer 1

以下实现基于最小堆(C++ 中的 std::priority_queue)，它记住“最佳” future 候选者。
重要的一点是对待基本解决方案k *(k+1)不同。由于这些数字可能占大多数，因此可以大大减少堆的大小。
在每个给定的时间，我们要么决定使用 k(k+1)数字，或使用当前最小堆的最高值。
每个使用的值都会导致在最小堆中插入一个新的候选者。
另一方面是只在堆中插入小于估计最大值的值，n(n+1) .
复杂度估计为 O(n log M)，其中 M 是堆的平均大小。
对于 n = 10^6 ，程序测得堆的最大大小等于9998，远小于n .
在我的 PC 上，我得到了 n = 10^6 的结果在 11 毫秒内。结果:977410038240
这是 C++ 代码。
这段代码记住了所有的序列，主要是为了调试。在实践中，如果我们只需要第 n 个值，则可以避免这种内存。如果效率仍然是一个问题，则也可以删除最大堆(对调试有用)大小的度量。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <chrono>

template <typename T>
void print (const std::vector<T> &A , const std::string &s = "") {
    std::cout << s;
    for (const T& val: A) {
            std::cout << val << " ";
    }
    std::cout << "\n";
}

struct Prod {
    long long p;    // product
    int last;       // last integer in the product
};

long long int consecutive_products (int n) {
    std::vector<long long> products;        // not strictly needed, for debugging
    products.reserve(n);
    products.push_back (2); products.push_back (6);
    
    long long max_val = (long long) n * (n+1);
    
    auto comp = [] (const Prod& x1, const Prod& x2) {
        if (x1.p == x2.p) return x1.last > x2.last;
        return x1.p > x2.p;
    };
    std::priority_queue<Prod, std::vector<Prod>, decltype(comp)> candidates(comp);
    if (n <= 2) return products[n-1];
    candidates.push ({24, 4});      // 2*3*4 -> extension of 2*3
    
    long long int prod_simple = 12; // = 3*4 - simple products k(k-1) are dealt with differently
    int rank_simple = 4;
    
    int index = 2;
    long long current_val = products[index - 1];
    Prod best;
    long long minval;
    int max_size = 0;
    while (index < n) {
        if (candidates.empty()) {
            minval = max_val;
        } else {
            best = candidates.top();
            minval = best.p;
        }
        if (minval <= prod_simple) {
            candidates.pop();
            long long new_product = minval * (best.last + 1);
            if (new_product < max_val) {
                candidates.push ({new_product, best.last + 1});
            }
        } else {
            minval = prod_simple;
            long long new_product = prod_simple * (rank_simple + 1);
            if (new_product < max_val) {
                candidates.push ({new_product, rank_simple + 1});
            }
            prod_simple = (long long) rank_simple * (rank_simple + 1);
            rank_simple++;
        }
        if (minval > current_val) {
            products.push_back(minval);
            current_val = minval;
            index++;
        }
        int size = candidates.size();
        if (size > max_size) max_size = size;
    }
    
    if (n <= 20) print (products, "Products: ");
    std::cout << "max heap size = " << max_size << std::endl;
    return minval;
}

int main() {
    int n;
    std::cout << "Enter n: ";
    std::cin >> n;
    auto t1 = std::chrono::high_resolution_clock::now();
    auto ans = consecutive_products (n);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout << ans << std::endl;
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
    std::cout << "duration = " << duration << " micro-s" << std::endl;  
    return 0;
}