Codewars中Twice Linear问题的Python解法优化求助

问题回顾 #

题目要求生成满足以下规则的升序无重复序列：

• 首元素u(0) = 1
• 对序列中每个元素x，2x+1和3x+1也属于该序列
• 最终返回序列的第n个元素（如dbl_linear(10)返回22）

原解法的问题 #

你当前的解法每次循环都对整个列表做去重+排序操作：

def dbl_linear(n):
    u_list= [1]
    for i in range(0, n+1):
        u_list.append(u_list[i] * 2 + 1)
        u_list.append(u_list[i] * 3 + 1)
        u_list= sorted(set(u_list))
    return u_list[n]

这种方式时间复杂度极高，每次sorted(set(u_list))的时间是O(k log k)（k为当前列表长度），当n达到6位数时，重复的排序和去重操作会导致严重超时。

优化方案：双指针法 #

利用序列严格递增的特性，用两个指针分别跟踪生成2x+1和3x+1的位置，每次只选择最小的有效元素加入序列，避免全量排序和去重：

1. 初始化序列u = [1]，两个指针i2和i3都从0开始，分别对应生成2*u[i2]+1和3*u[i3]+1的索引
2. 循环直到序列长度超过n：
   • 计算两个候选值y = 2*u[i2] + 1和z = 3*u[i3] + 1
   • 若y < z：将y加入序列，i2右移一位（当前i2对应的元素已生成过y）
   • 若y == z：将y加入序列，同时右移i2和i3（避免重复生成相同元素）
   • 若z < y：将z加入序列，i3右移一位
3. 最终返回u[n]

优化后的代码 #

def dbl_linear(n):
    u = [1]
    i2 = i3 = 0
    while len(u) <= n:
        y = 2 * u[i2] + 1
        z = 3 * u[i3] + 1
        if y < z:
            u.append(y)
            i2 += 1
        elif y > z:
            u.append(z)
            i3 += 1
        else:
            u.append(y)
            i2 += 1
            i3 += 1
    return u[n]

效率说明 #

这个方法的时间复杂度是O(n)，每个元素只被处理一次，没有多余的排序和去重操作，即使n是6位数也能快速运行。

内容的提问来源于stack exchange，提问作者lncht_mn