如何找到一个系列的公式

Question

我最近遇到了一个问题。

问题=>

给定 n，k，我们必须找出序列中第 k 个索引处的数字。（未给出系列我们必须逻辑生成它以找到系列中的第 k 个元素）

系列图案请看例子

（索引是从 1 开始而不是从 0 开始）。

例子=>

n=4, k=5
series = 1, 2, 3, 4, 1, 2, 3, 1, 2, 1
answer = 1 (because it is at 5th index, index is from 1).

示例=>

n=5, k=8
series = 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 3, 1, 2, 1
answer=3 (because 3 is at 8th index).

我想在 O(1) 时间复杂度内执行此操作。是否有任何公式或其他方法可以做到这一点？

Answer 1

我不知道那里可能有公式，但你可能应该在数学论坛上问这个问题。

我会做以下几行：

while(K > N) {
 K= K - N
 N=N-1;
}

while 停止时，这里的 K 将是您的答案。它不是公式，但应该比生成数组和获取第 k 个索引更快。

Answer 2

您的系列可以按三角形组织，例如 n = 4:

1  2  3  4          1  2  3  4
1  2  3             5  6  7
1  2                8  9 
1                  10

（值在左边，索引 k 在右边。索引 k 必须在 [1; N] 中，其中 N = n · (n + 1) / 2]。）你可以反转三角形：

1                  10                   0
1  2                8  9                1  2
1  2  3             5  6  7             3  4  5
1  2  3  4          1  2  3  4          6  7  8  10

最右边是倒序的从零开始的索引。每行第 i 个数是三角数 T(i) = i · (i + 1) / 2.

你可以用

找到倒三角的第i行（从零开始）

i = floor(−½ + math.sqrt(½ + 2·(N − k)))

该行的第一个索引是

T=T(i)=i·(i+1)/2

从起始索引 T 和倒三角形中的搜索索引 N − k，您可以得到您的值，但您必须从该行的末尾开始计数：

res(n, k) = i + 1 − (N − k − T)

很抱歉，由于反复颠倒和从基于一的索引切换到基于零的索引，反之亦然，解释有点混乱。下面是一些 Python 实现上述内容的代码：

def value(n, k):
    N = n * (n + 1) // 2            # length of series
    K = N - k                       # inverted index, zero-based
    
    i = int(-1 + math.sqrt(1 + 8*K)) // 2
    T = i * (i + 1) // 2            # row and its starting index
    
    return i + 1 - (K - T)

如何找到一个系列的公式

How to find the formula of a series

algorithm

math

mathematical-optimization