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

Question

我最近遇到了这个问题：

存在一个通过任意两个或多个连续自然数相乘形成的（递增）排序数组。

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

例如。 2 由两个连续的自然数 1 和 2 组成：2 = 1×2。 6 = 2×3 或 1×2×3, 20 = 4×5。

如果给定 n 作为参数，则从上面的数组中找到第 n 个数字并返回。

限制

• 1 ≤ n ≤ 1000000
仅当答案小于 10
• 12 时才给出n

所以在这里我能够找到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;
}

Answer 2

import heapq


def factorial(x):
    fact = 1
    for i in range(1, x + 1): 
        fact *= i
    return fact


def nth_number(k):
    heap = [(2, 1, 2)]
    heapq.heapify(heap)
    size_fact = 2
    cur_factorial = factorial(size_fact)
    cur_number = -1
    i = 1
    while i <= k:
        x_number, start_from, size = heapq.heappop(heap) 
        if x_number > cur_number:
            if x_number == cur_factorial:
                # Insert the next factorial as well
                size_fact += 1
                cur_factorial = factorial(size_fact)
                heapq.heappush(heap, (cur_factorial, 1, size_fact)) 
            cur_number = x_number
            i += 1
        heapq.heappush(heap, (x_number / start_from * (start_from + size), start_from + 1, size))

    return cur_number


# Test the function
print(int(nth_number(4)))  # Output the 10th number in the sequence