每日一题的第55题，答案不同
有一个数列u，使得u符合以下规则：1、u的第一个数字是1.
2、对于u中的每一个x，都有y=2*x+1 和z=3*x+1，且y和z都在u中。
3、u中没有其他数字。
复制代码
例如:
u =
复制代码
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。
例如： 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, q3)
if h == q2: h = q2.popleft()
if h == q3: h = q3.popleft()
cnt += 1
输出是2911582。花费1s不到....
我的代码：
from timeit import timeit
def dlb_linear(n):
u =
length = len(u)
num = 0
while length <= n:
x = 2 * u + 1
y = 3 * u + 1
u.append(x)
u.append(y)
u.sort(reverse = False)
length = len(u)
num += 1
print(u)
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:34 编辑
你的问题在于这一句
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 是变化的
页:
[1]