查找满足一组条件的数字序列的算法

Question

问题

给定一个整数列表，确定序列中连续数字恰好与 N 个索引相距的值等于 N 乘以序列中的前一个数字。

规则:

• N必须大于1

• 少于 3 个条目的序列应该是忽略

• 返回的序列必须始终是最长的N的给定值

• 全零的序列不算数

我的解决方案

1. 迭代长度为M的数字列表

2. 在每次迭代中:

   1.a 分别在current_number 和current_index 中保存当前编号和当前索引。

   1.b 计算current_number 可以容纳的连续数字序列的最大可能数量，并将此数字保存在nested_iteration_count 中。

   1.c 以 nested_iteration_count 的循环计数和 N 的最小可能值 N = 2 开始嵌套迭代

   1.c.1 检查序列是否存在。如果存在，将该序列存入数组

   1.c.2 将 N 加 1 并重复循环，直到内循环迭代完成。

3. 为下一个数字重复外循环

示例

考虑以下整数列表:

数字 2 10 4 3 8 6 9 9 18 27

索引 0 1 2 3 4 5 6 7 8 9

找到以下序列:

• 2, 4, 8
• 3、9、27

这个算法显然有 O(n^2) 复杂度。是否可以对此进行改进？

Answer 1

使用@user3386109 优化的快速 Python 实现

第一阶段检查乘数N的进展是否从第i项继续

第二阶段 - 检索每个 N 的最长序列 - 可能会更简洁

res 包含最长的 (N:(count, endingindex) {2: (3, 4), 3: (3, 9) }

import math
lst = [2,10,4,3,8,6,9,9,18,27]
l = len(lst)
mp = {}
mn = min(lst)
mx = max(lst)
nmax = int(math.sqrt(mx / mn))
for i in range(2, l):
    for n in range(2, min(i, (l - 1)//2, nmax) + 1):
        if lst[i - n] * n == lst[i]:
            t = (i-n, n)
            le = mp[t] if t in mp else 1
            mp[(i, n)] = le + 1

res = {}
for x in mp:
    n = x[1]
    le = mp[x]
    ending = x[0]
    if n in res:
        if res[n][0] < le:
            res[n] = (le, ending)
    else:
        res[n] = (le, ending)

print(mp)
print(res)

{(2, 2): 2, (4, 2): 3, (5, 2): 2, (6, 3): 2, (8, 2): 2, (8, 3): 2, (9, 3): 3}
{2: (3, 4), 3: (3, 9)}