[已解决]每日一题的第55题，答案不同

白本羽

有一个数列u，使得u符合以下规则：
1、u的第一个数字是1.
2、对于u中的每一个x，都有y=2*x+1 和z=3*x+1，且y和z都在u中。
3、u中没有其他数字。
复制代码

例如:
u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]
复制代码


1  --->  y(1) = 3  ,z(1) = 4
3  --->  y(3) = 7  ,z(3) = 10
4  --->  y(4) = 9  ,z(4) = 13
....

要求：给出函数dbl_linear(n)，  返回按顺序排列的u[n]。
例如： dlb_linear(10) 返回  22.
注意：请考虑效率问题（1<n<100000）

参考答案的代码：

from collections import deque


def dbl_linear1(n):
    h = 1
    cnt = 0
    q2, q3 = deque([]), deque([])
    while True:
        if (cnt >= n):
            return h
        q2.append(2 * h + 1)
        q3.append(3 * h + 1)
        h = min(q2[0], q3[0])
        if h == q2[0]: h = q2.popleft()
        if h == q3[0]: h = q3.popleft()
        cnt += 1

输出是2911582。花费1s不到....

我的代码：

from timeit import timeit


def dlb_linear(n):
    u = [1]
    length = len(u)
    num = 0
    while length <= n:
        x = 2 * u[num] + 1
        y = 3 * u[num] + 1
        u.append(x)
        u.append(y)
        u.sort(reverse = False)
        length = len(u)
        num += 1
    print(u[n])
    print(u)
    return u


t = timeit("dlb_linear(100000)", 'from __main__ import dlb_linear', number = 1)
print(t)

输出是2942626,花费9.22s

如果题目中的u列表是按从小到大排序的，那么x和y的生成也应该是从小到大，求指点哪里出了问题...为什么输出不一样?

最佳答案

月排行榜 / 总排行榜

qq1151985918

2021-5-13 09:20:53

你的问题在于这一句  

1  --->  y(1) = 3  ,z(1) = 4
3  --->  y(3) = 7  ,z(3) = 10
4  --->  y(4) = 9  ,z(4) = 13

理解不到位

实际上 y(4) < z(3) 这种情况你就没有作出处理，所以才会错误
而且你的 数组 u 在不断进行排序过程，索引值 num 是变化的

跳转到最佳答案楼层

qq1151985918

你的问题在于这一句  

1  --->  y(1) = 3  ,z(1) = 4
3  --->  y(3) = 7  ,z(3) = 10
4  --->  y(4) = 9  ,z(4) = 13

理解不到位

实际上 y(4) < z(3) 这种情况你就没有作出处理，所以才会错误
而且你的 数组 u 在不断进行排序过程，索引值 num 是变化的