[已解决]每日一题的第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）

参考答案的代码：

1. from collections import deque
   
2. 
   
3. 
   
4. def dbl_linear1(n):
   
5.     h = 1
   
6.     cnt = 0
   
7.     q2, q3 = deque([]), deque([])
   
8.     while True:
   
9.         if (cnt >= n):
   
10.             return h
    
11.         q2.append(2 * h + 1)
    
12.         q3.append(3 * h + 1)
    
13.         h = min(q2[0], q3[0])
    
14.         if h == q2[0]: h = q2.popleft()
    
15.         if h == q3[0]: h = q3.popleft()
    
16.         cnt += 1

复制代码

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

我的代码：

1. from timeit import timeit
   
2. 
   
3. 
   
4. def dlb_linear(n):
   
5.     u = [1]
   
6.     length = len(u)
   
7.     num = 0
   
8.     while length <= n:
   
9.         x = 2 * u[num] + 1
   
10.         y = 3 * u[num] + 1
    
11.         u.append(x)
    
12.         u.append(y)
    
13.         u.sort(reverse = False)
    
14.         length = len(u)
    
15.         num += 1
    
16.     print(u[n])
    
17.     print(u)
    
18.     return u
    
19. 
    
20. 
    
21. t = timeit("dlb_linear(100000)", 'from __main__ import dlb_linear', number = 1)
    
22. 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 是变化的