Python: 每日一题 55
本帖最后由 ooxx7788 于 2017-5-26 16:56 编辑马上要放假了，今日再来一题。Sixpy说题目越来越简单，那就出个难点的(4kyu)。
有一个数列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）
jerry已经把答案做出来了，我就先把答案放出来吧。我自己写的答案在6楼，这里提供的是一个网络上面比较高效的答案。
**** Hidden Message ***** 本帖最后由 jerryxjr1220 于 2017-5-26 16:12 编辑
感觉效率可能是问题
def dbl_linear(n):
def addin(num):
if num not in s:
u.append(num)
s.add(num)
u =
s = set(u)
i = 1
while len(s) < n * 1.2:
addin(u * 2 + 1)
addin(u * 3 + 1)
u.sort()
i += 1
return u
print(dbl_linear(10000)) 不用排序的方法，改插入法，时间可以缩短一半
def dbl_linear(n):
def addin(num):
if num not in s:
s.add(num)
for i in range(len(u) - 1, 0, -1):
if u < num:
u.insert(i + 1, num)
return
u =
s = set(u)
i = 1
while len(s) < n * 1.2:
addin(u * 2 + 1)
addin(u * 3 + 1)
i += 1
return u
print(dbl_linear(10000)) jerryxjr1220 发表于 2017-5-26 16:11
感觉效率可能是问题
效率确实低了，我电脑上面n = 100000时候，用了84秒。我的只跑了1.8秒。
而且结果还有个问题，算n=100000 和n=10000结果都对，但是算n=20时候，结果应该是57，你的计算结果是58.n的倍数要调大一些结果才对。但是n的结果调大了，函数的计算效率就更低了。 本帖最后由 jerryxjr1220 于 2017-5-26 16:50 编辑
ooxx7788 发表于 2017-5-26 16:33
效率确实低了，我电脑上面n = 100000时候，用了84秒。我的只跑了1.8秒。
而且结果还有个问题，算n=10000 ...
要么就是死命加倍数，反正只要倍数足够大，总归可以涵盖的。。。
def dbl_linear(n):
def addin(num):
if num not in s:
s.add(num)
u.append(num)
u =
s = set(u)
i = 1
while len(s) < n * 10:
addin(u * 2 + 1)
addin(u * 3 + 1)
i += 1
u.sort()
return u
print(dbl_linear(100000))
这样1秒就可以出答案了。。。
2911582
jerryxjr1220 发表于 2017-5-26 16:45
要么就是死命加倍数，反正只要倍数足够大，总归可以涵盖的。。。
这样1秒就可以出答案了。。。
其实根本不需要addin和set的部分。
例如，我就是这样写的。原题里面更新一个用双端队列模块写的，效率比我写的高可能有10倍。{:10_266:}
def dbl_linear(n):
u =
i = 0
while len(u) < n * 10:
u.append(u * 2 + 1)
u.append(u * 3 + 1)
i += 1
return sorted(list(set(u))) ooxx7788 发表于 2017-5-26 16:53
其实根本不需要addin和set的部分。
例如，我就是这样写的。原题里面更新一个用双端队列模块写的，效率 ...
嗯，我这2个函数是根据原来的思路改过来的，如果是单纯的只要加大n的倍数的话，确实不需要addin和set部分了。 两个函数，题目没说重复的元素怎么算？假设重复的也算在列表里面
关键应该是知道什么时候停止
把这个按照二叉树画出来，发现这玩意就是堆排序的最小堆
那要得n个数，就要 m =logn(2为底数)，取顶函数，得到层数 m
如果在第 k 层的最左分支比第 m 层最右分支大，就可以停止了
# 用列表
def dbl_linear(n):
s =
m = math.ceil(math.log(n,2))
i,j,max_num,min_num =0,0,1,1
while i<m:
max_num = 3*max_num+1
i +=1
while min_num < max_num:
min_num = 2*min_num+1
j +=1
for k in range(2**j):
s.extend(+1,3*s+1])
if len(s)>=2**j:
break
s = sorted(s)
return s
换一种问法，就是找到我没排序之前的第 n 个数 s，找出所有比它小的数
最左分支是一路 2*x+1 下来，每一层最小一定是最左，这个数比 s小，则后面排除
def dbl_linear2(n):
s =
m = 1
for i in range(n):
s.extend(+1,3*s+1])
while m<s:
m = 2*m +1
for j in range(n,m):
s.extend(+1,3*s+1])
if 2*s+1==m:
break
s = sorted(s)
return s
如果重复的不算，那结果就先用set（）过一遍，再索引
最终耗时,n=100000时, 4.7s，有点慢 本帖最后由 kwty 于 2018-2-10 17:24 编辑
from time import clock
clock()
list1 =
n = 100000
c = list1
while len(list1) < n + 1:
L1 =
L2 =
c = []
c.extend(L1)
c.extend(L2)
list1.extend(L1)
list1.extend(L2)
list1 = list(set(list1))
list1.sort()
print(list1,clock())
4487787 0.17909268667594722 自己想不出来 学习一下 看看答案 看答案 答案呢？ 看看 1 sorted(list(set(u))) 是参考楼主的
自己的for循环比楼主的while循环快一丢丢，嘻嘻
# 自己的代码
def dlb_linear(n):
u =
for i in range(n * 5):
u.append(u * 2 + 1)
u.append(u * 3 + 1)
print(sorted(list(set(u))))
# 楼主的代码
def dbl_linear(n):
u =
i = 0
while len(u) < n * 10:
u.append(u * 2 + 1)
u.append(u * 3 + 1)
i += 1
print(sorted(list(set(u))))
本机测试 n = 100000 时
2911582
用时： 0.7678713798522949
2911582
用时： 0.8851046562194824 本机测试了 n = 1000000 时的结果
自己的答案和楼主的答案一致，跟隐藏的代码答案不一致，结果是隐藏的代码答案正确。。。
用时少答案还准确，太厉害了
# 自己的
54383518
用时： 7.671760559082031
# 楼主的
54383518
用时： 8.959300994873047
# 隐藏的
54381286
用时： 1.1793506145477295 def dlb_linear(n):
list_z =
i = 0
while len(list_z)<=n:
list_z.append(2*list_z+1)
list_z.append(3*list_z+1)
i+=1
# list_reulst = list_z.sort()
list_reulst = sorted(list_z)
return list_reulst
print(dlb_linear(10)) 学习了
页:
[1]
2