Python: 每日一题 55

ooxx7788

马上要放假了，今日再来一题。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, 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

感觉效率可能是问题

def dbl_linear(n):
    def addin(num):
        if num not in s:
            u.append(num)
            s.add(num)
    u = [1, 3, 4]
    s = set(u)
    i = 1
    while len(s) < n * 1.2:
        addin(u[i] * 2 + 1)
        addin(u[i] * 3 + 1)
        u.sort()
        i += 1
    return u[n]

print(dbl_linear(10000))

jerryxjr1220

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

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[i] < num:
                    u.insert(i + 1, num)
                    return

    u = [1, 3, 4]
    s = set(u)
    i = 1
    while len(s) < n * 1.2:
        addin(u[i] * 2 + 1)
        addin(u[i] * 3 + 1)
        i += 1
    return u[n]

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

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

def dbl_linear(n):
    def addin(num):
        if num not in s:
            s.add(num)
            u.append(num)

    u = [1, 3, 4]
    s = set(u)
    i = 1
    while len(s) < n * 10:
        addin(u[i] * 2 + 1)
        addin(u[i] * 3 + 1)
        i += 1
    u.sort()
    return u[n]

print(dbl_linear(100000))

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

ooxx7788

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

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

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

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

def dbl_linear(n):
    u = [1]
    i = 0
    while len(u) < n * 10:
        u.append(u[i] * 2 + 1)
        u.append(u[i] * 3 + 1)
        i += 1
    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 层最右分支大，就可以停止了

# 用列表
def dbl_linear(n):
    s = [1]
    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([2*s[k]+1,3*s[k]+1])
        if len(s)>=2**j:
            break
    s = sorted(s)
    return s[n]

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

def dbl_linear2(n):
    s = [1]
    m = 1
    for i in range(n):
        s.extend([2*s[i]+1,3*s[i]+1])
    while m<s[n]:
        m = 2*m +1
    for j in range(n,m):
        s.extend([2*s[j]+1,3*s[j]+1])
        if 2*s[i]+1==m:
            break
    s = sorted(s)
    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循环快一丢丢，嘻嘻

# 自己的代码
def dlb_linear(n):
    u = [1]
    for i in range(n * 5):
        u.append(u[i] * 2 + 1)
        u.append(u[i] * 3 + 1)
    print(sorted(list(set(u)))[n])

# 楼主的代码
def dbl_linear(n):
    u = [1]
    i = 0
    while len(u) < n * 10:
        u.append(u[i] * 2 + 1)
        u.append(u[i] * 3 + 1)
        i += 1
    print(sorted(list(set(u)))[n])

本机测试 n = 100000 时
2911582
用时： 0.7678713798522949
2911582
用时： 0.8851046562194824

小陨aoq

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

# 自己的
54383518
用时： 7.671760559082031
# 楼主的
54383518
用时： 8.959300994873047
# 隐藏的
54381286
用时： 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

学习了