从由任意两个或多个连续自然数相乘形成的排序数组中找到第 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(n²) 解决方案，但我想知道是否有更好的解决方案.

我的O(n²)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），它会记住“最佳”未来候选对象。

重要的一点是要区别对待基本解决方案k *(k+1)。由于这些数字很可能占多数，因此可以大大减小堆的大小。

在每个给定时间，我们要么决定使用一个 k(k+1) 数字，要么使用最小堆的当前最高值。每个使用的值都会导致在最小堆中插入一个新的候选值。

另一方面是只在堆中插入小于估计最大值的值，n(n+1)。

复杂度估计为 O(n log M)，其中 M 是堆的平均大小。

对于n = 10^6，程序测得堆的最大大小等于9998，远小于n。

在我的电脑上，我在 11 毫秒内得到了 n = 10^6 的结果。结果：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;
}

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

Find Nth number from a sorted array formed by multiplying any two or more consecutive natural numbers

arrays

sorting

algorithm

product

subset