高效的隊列deque

今天這一題有點燒腦：

有一個序列u，滿足：

1. 第一個元素是1

2. 此後任意一個元素x，2x+1和3x+1也必定在u中

現給定整數n，求序列u中的第n+1個元素是什麼？

規定：要註意演算法的效率

分析：

乍一想有點亂。先找幾個數計算一下：

1

[1], 3, 4

1, [3], 4, 7, 10

1, 3, [4], 7, 9, 10, 13

其中這個9提醒我們，雖然單純的2x+1或3x+1一定是遞增的，但是前一個數的3x+1有可能大於後一個數的2x+1。因此，當要在序列u中取“下一個數”計算它的2x+1和3x+1時，如何選取？

笨辦法是用一個列表保存序列u，每計算出一個新的2x+1和3x+1時，都遍歷一遍當前的列表，然後找到適當的位置插入。這顯然不符合本題對於效率的要求。

換一個角度思考：如果我們不是用一個列表，而是用兩個列表表示序列u呢？這兩個列表分別保存2x+1和3x+1的值。由於它們一定是遞增的，新元素只要直接append在隊尾即可。而“選取下一個數”的動作，相當於從兩個列表的隊首依次挑出較小的那一個。這道題目進一步變形為：兩個已經各自按從小到大順序排列的列表，如何合併為一個從小到大排序的列表？

實現要點：

1. 高效的隊列：

用deque。這篇文章比較了deque, queue, 和list的性能。

2. 兩個已經各自按從小到大順序排列的列表，如何合併為一個從小到大排序的列表？

取兩個隊首的最小值，並pop該最小值元素。下一次迴圈仍然取兩個隊首的最小值。

代碼參考：

from collections import deque

def dbl_linear(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[0], q3[0])
        if h == q2[0]: h = q2.popleft()
        if h == q3[0]: h = q3.popleft()
        cnt += 1