Python: 每日一题 55

ooxx7788

马上要放假了，今日再来一题。Sixpy说题目越来越简单，那就出个难点的(4kyu)。

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

复制代码

例如:

1. 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）

jerry已经把答案做出来了，我就先把答案放出来吧。我自己写的答案在6楼，这里提供的是一个网络上面比较高效的答案。

游客，如果您要查看本帖隐藏内容请回复

jerryxjr1220

感觉效率可能是问题

1. def dbl_linear(n):
   
2.     def addin(num):
   
3.         if num not in s:
   
4.             u.append(num)
   
5.             s.add(num)
   
6.     u = [1, 3, 4]
   
7.     s = set(u)
   
8.     i = 1
   
9.     while len(s) < n * 1.2:
   
10.         addin(u[i] * 2 + 1)
    
11.         addin(u[i] * 3 + 1)
    
12.         u.sort()
    
13.         i += 1
    
14.     return u[n]
    
15. 
    
16. print(dbl_linear(10000))

复制代码

jerryxjr1220

不用排序的方法，改插入法，时间可以缩短一半

1. def dbl_linear(n):
   
2.     def addin(num):
   
3.         if num not in s:
   
4.             s.add(num)
   
5.             for i in range(len(u) - 1, 0, -1):
   
6.                 if u[i] < num:
   
7.                     u.insert(i + 1, num)
   
8.                     return
   
9. 
   
10.     u = [1, 3, 4]
    
11.     s = set(u)
    
12.     i = 1
    
13.     while len(s) < n * 1.2:
    
14.         addin(u[i] * 2 + 1)
    
15.         addin(u[i] * 3 + 1)
    
16.         i += 1
    
17.     return u[n]
    
18. 
    
19. print(dbl_linear(10000))

复制代码

ooxx7788

jerryxjr1220 发表于 2017-5-26 16:11
感觉效率可能是问题

效率确实低了，我电脑上面n = 100000时候，用了84秒。我的只跑了1.8秒。
而且结果还有个问题，算n=100000 和n=10000结果都对，但是算n=20时候，结果应该是57，你的计算结果是58.  n的倍数要调大一些结果才对。但是n的结果调大了，函数的计算效率就更低了。

jerryxjr1220

ooxx7788 发表于 2017-5-26 16:33
效率确实低了，我电脑上面n = 100000时候，用了84秒。我的只跑了1.8秒。
而且结果还有个问题，算n=10000 ...

要么就是死命加倍数，反正只要倍数足够大，总归可以涵盖的。。。

1. def dbl_linear(n):
   
2.     def addin(num):
   
3.         if num not in s:
   
4.             s.add(num)
   
5.             u.append(num)
   
6. 
   
7.     u = [1, 3, 4]
   
8.     s = set(u)
   
9.     i = 1
   
10.     while len(s) < n * 10:
    
11.         addin(u[i] * 2 + 1)
    
12.         addin(u[i] * 3 + 1)
    
13.         i += 1
    
14.     u.sort()
    
15.     return u[n]
    
16. 
    
17. print(dbl_linear(100000))

复制代码

这样1秒就可以出答案了。。。
2911582
[Finished in 1.2s]

ooxx7788

jerryxjr1220 发表于 2017-5-26 16:45
要么就是死命加倍数，反正只要倍数足够大，总归可以涵盖的。。。

这样1秒就可以出答案了。。。

其实根本不需要addin和set的部分。

例如，我就是这样写的。原题里面更新一个用双端队列模块写的，效率比我写的高可能有10倍。

1. def dbl_linear(n):
   
2.     u = [1]
   
3.     i = 0
   
4.     while len(u) < n * 10:
   
5.         u.append(u[i] * 2 + 1)
   
6.         u.append(u[i] * 3 + 1)
   
7.         i += 1
   
8.     return sorted(list(set(u)))[n]

复制代码

jerryxjr1220

ooxx7788 发表于 2017-5-26 16:53
其实根本不需要addin和set的部分。

例如，我就是这样写的。原题里面更新一个用双端队列模块写的，效率 ...

嗯，我这2个函数是根据原来的思路改过来的，如果是单纯的只要加大n的倍数的话，确实不需要addin和set部分了。

solomonxian

两个函数，题目没说重复的元素怎么算？假设重复的也算在列表里面
关键应该是知道什么时候停止

把这个按照二叉树画出来，发现这玩意就是堆排序的最小堆
那要得n个数，就要 m =logn(2为底数)，取顶函数，得到层数 m
如果在第 k 层的最左分支比第 m 层最右分支大，就可以停止了

1. # 用列表
   
2. def dbl_linear(n):
   
3.     s = [1]
   
4.     m = math.ceil(math.log(n,2))
   
5.     i,j,max_num,min_num =0,0,1,1
   
6.     while i<m:
   
7.         max_num = 3*max_num+1
   
8.         i +=1
   
9.     while min_num < max_num:
   
10.         min_num = 2*min_num+1
    
11.         j +=1
    
12.         
    
13.     for k in range(2**j):
    
14.         s.extend([2*s[k]+1,3*s[k]+1])
    
15.         if len(s)>=2**j:
    
16.             break
    
17.     s = sorted(s)
    
18.     return s[n]

复制代码

换一种问法，就是找到我没排序之前的第 n 个数 s[n]，找出所有比它小的数
最左分支是一路 2*x+1 下来，每一层最小一定是最左，这个数比 s[n]小，则后面排除

1. def dbl_linear2(n):
   
2.     s = [1]
   
3.     m = 1
   
4.     for i in range(n):
   
5.         s.extend([2*s[i]+1,3*s[i]+1])
   
6.     while m<s[n]:
   
7.         m = 2*m +1
   
8.     for j in range(n,m):
   
9.         s.extend([2*s[j]+1,3*s[j]+1])
   
10.         if 2*s[i]+1==m:
    
11.             break
    
12.     s = sorted(s)
    
13.     return s[n]

复制代码

如果重复的不算，那结果就先用set（）过一遍，再索引
最终耗时,n=100000时, 4.7s，有点慢

kwty

from time import clock
clock()
list1 = [1]
n = 100000
c = list1
while len(list1) < n + 1:
        L1 = [2 * i + 1 for i in c]
        L2 = [3 * i + 1 for i in c]
        c = []
        c.extend(L1)
        c.extend(L2)
        list1.extend(L1)
        list1.extend(L2)
        list1 = list(set(list1))
list1.sort()

print(list1[n],clock())


4487787 0.17909268667594722

ciager

自己想不出来

小强工作室

学习一下

pan_back

看看答案

Geoffreylee

看答案

kinkon

答案呢？

holiday_python

看看

19971023

1

小陨aoq

sorted(list(set(u)))[n] 是参考楼主的
自己的for循环比楼主的while循环快一丢丢，嘻嘻

1. # 自己的代码
   
2. def dlb_linear(n):
   
3.     u = [1]
   
4.     for i in range(n * 5):
   
5.         u.append(u[i] * 2 + 1)
   
6.         u.append(u[i] * 3 + 1)
   
7.     print(sorted(list(set(u)))[n])
   
8. 
   
9. # 楼主的代码
   
10. def dbl_linear(n):
    
11.     u = [1]
    
12.     i = 0
    
13.     while len(u) < n * 10:
    
14.         u.append(u[i] * 2 + 1)
    
15.         u.append(u[i] * 3 + 1)
    
16.         i += 1
    
17.     print(sorted(list(set(u)))[n])

复制代码

1. 本机测试 n = 100000 时
   
2. 2911582
   
3. 用时： 0.7678713798522949
   
4. 2911582
   
5. 用时： 0.8851046562194824

复制代码

小陨aoq

本机测试了 n = 1000000 时的结果
自己的答案和楼主的答案一致，跟隐藏的代码答案不一致，结果是隐藏的代码答案正确。。。
用时少答案还准确，太厉害了

1. 
   
2. # 自己的
   
3. 54383518
   
4. 用时： 7.671760559082031
   
5. # 楼主的
   
6. 54383518
   
7. 用时： 8.959300994873047
   
8. # 隐藏的
   
9. 54381286
   
10. 用时： 1.1793506145477295

复制代码

nononoyes

def dlb_linear(n):
    list_z = [1]
    i = 0
    while len(list_z)<=n:
        list_z.append(2*list_z[i]+1)
        list_z.append(3*list_z[i]+1)
        i+=1
    # list_reulst = list_z.sort()
    list_reulst = sorted(list_z)
    return list_reulst[n]

print(dlb_linear(10))

y116114

学习了