剑指 Offer2（Python 版）解析（Ch5）

具体实现和测试代码：

系列解析（TBD）：

  • Python 单例模式
  • 好玩儿的 DP
  • 递归还是递归
  • 双指针的威力
  • 双列表的威力
  • 有趣的排列组合

特别说明：下文中的实例代码一般仅包括核心算法（不一定能直接运行），完整代码可以参考对应的链接。

第五章：优化时间和空间效率

面试题 39：数组中出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组 {1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。

最简单的方法就是先排序，取中间的数字就肯定是了，当然也可以用字典把每个元素的出现次数记录下来，超过数组长度一半就返回。

书中介绍了两种算法，时间复杂度与字典的方式一样，但空间复杂度为 O(1)。第一种是基于 Partition 的思路，和快排的其中一步类似：

  • 随机选择一个数字
  • 比该数字小的放在它的左边，大的放在右边
  • 如果选中数字的下标正好是中位数的位置，那这个数字肯定就是出现次数超过一般的数字
  • 如果选中数字的下标小于中位数的位置，中位数在它的右边；否则在左边

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def mth(lst):
    mid = len(lst) // 2
    loc = 0
    lst = partition(lst, loc)
    while loc != mid:
        if loc > mid:
            loc -= 1
            lst = partition(lst, loc)
        else:
            loc += 1
            lst = partition(lst, loc)
        if check(lst, lst[mid]):
            return lst[mid]
    return 0

def check(lst, val):
    k = 0
    for i in lst:
        if i == val:
            k += 1
    return 2 * k > len(lst)

def partition(lst, loc):
    pi = lst[loc]
    small = [i for i in lst if i < pi]
    big = [i for i in lst if i >= pi]
    return small + big

还有一种解法是我自己比较喜欢的，基本思想是出现次数超过一半的数字，次数必然超过其他所有数字次数和。具体而言，从第二个数字开始，如果和第一个数字一样，次数加一，否则次数减一；当次数为零时，重新将次数置为 1 并保存对应的数字。最后将次数置为 1 时对应的数字一定是要找的数字。

1
2
3
4
5
6
7
8
9
10
11
12
def mth(lst):
    times = 1
    num = lst[0]
    for i in lst[1:]:
        if i == num:
            times += 1
        else:
            times -= 1
        if times == 0:
            times = 1
            num = i
     return check(lst, num)

这道题需要特别注意的是 check 函数，其目的就是确保选定的数字出现次数 “超过一半”，而不仅仅是最多。比如 [1,2,3,2,4,2,5,2]，如果你直接 return num 的话就会得到 2，其实是出现次数最多的，并不是超过一半的。

具体实现和测试代码可参考：39_MoreThanHalfNumber

面试题 40：最小的 k 个数

题目：输入 n 个整数，找出其中最小的 k 个数。例如输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4。

常规解法就不赘述了。书中第一种解法是基于 Partition 的，也就是比选中的数字小的正好是 k 个的时候，我们可以让 Partition 函数返回拆分后的比选中数字小和一样大的两个子序列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def kmins(lst, k):
    loc = 0
    sml, eql = partition(lst, loc)
    while len(sml) < k or len(sml + eql) < k:
        loc += 1
        sml, eql = partition(lst, loc)
    return (sml + eql)[:k]

def partition(lst, loc):
    sml, eql = [], []
    pi = lst[loc]
    for i in lst:
        if i < pi:
            sml.append(i)
        elif i == pi:
            eql.append(i)
    return sml, eql

不过我觉得最简单的思路应该是选择排序的方式，依次 pop 出最小的值：

1
2
3
4
5
6
7
def kmins(lst, k):
    result = []
    while lst and len(result) < k:
        minn = min(lst)
        result.append(minn)
        lst.remove(minn)
    return result

书中还介绍了一种基于容器的算法，在数据量很大的时候比较好（数字 sequence 不用一次全部读入内存）。主要思路是用一个 k 大小的容器，数据遍历时同步更新这个容器。容器这里选择最小堆比较高效：

1
2
3
4
5
6
7
8
def kmins(lst, k):
    import heapq
    container = lst[:k]
    heapq._heapify_max(container)
    for i in lst[k:]:
        if i < container[0]:
            heapq._heapreplace_max(container, i)
    return [heapq._heappop_max(container) for i in range(k)]

最后需要说明的是，本题和上题用的 Partition 并不是唯一的方式。

具体实现和测试代码可参考：40_KLeastNumbers

面试题 41：数据流中的中位数

题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

由于是从数据流中读入的，所以数据的数量会发生变化，也就意味着整个过程中位数可能会发生变化。而数据需要存入容器，选择不同的容器效果不同（注：表格来自书籍 P215）：

数据结构 插入时间复杂度 得到中位数时间复杂度
没有排序的数组 O(1) O(N)
排序的数组 O(N) O(1)
排序的链表 O(N) O(1)
二叉搜索树 平均 O(logN) 最差 O(N) 平均 O(logN) 最差 O(N)
AVL（平衡二叉搜索）树 O(logN) O(1)
最大堆和最小堆 O(logN) O(1)

需要注意的是，AVL 树需要把左右节点的高度差调整为节点数量差。

用最大堆和最小堆其实和 AVL 树有些类似，主要思想是让其中一个堆的所有值都大于（或小于）另一个堆，且两堆的数量相等或相差为 1。具体而言：

  • 第奇数个和偶数个数字分别放在两个堆（数量保证）。
  • 如果新的要放在最大堆的数字比最小堆的堆顶（最小值）要大，就把最小堆的堆顶替换；反之亦然（保证最小堆的所有数字都大于最大堆）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import heapq

def get_heaps(lst):
    minh, maxh = [], []
    for i, v in enumerate(lst):
        # 偶数放入最大堆
        if i % 2 == 0:
            if minh and v > minh[0]:
                # 把 v 放进去并替换出来一个小的
                v = heapq.heapreplace(minh, v)
            # 注意换成负数，因为实际用的是最小堆
            heapq.heappush(maxh, -v)
        else:
            # 因为存进去的是 -v，所以出来的时候要还原
            if maxh and v < -maxh[0]:
                v = -heapq.heapreplace(maxh, -v)
            heapq.heappush(minh, v)
    return minh, maxh

注意，这里我们用最小堆取负数来模拟最大堆，所以进入最大堆的都要取负，出来时同样也要取负。剩下的就很简单了，不再赘述，稍微需要注意的是，数量为奇数时，取最大堆的堆顶，因为最大堆多放了一个数字；否则取两个堆顶的均值。

具体实现和测试代码可参考：41_StreamMedian

面试题 42：连续子数组的最大和

题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O (n)。

经典题目，DP 的思想。先按常规解法：

1
2
3
4
5
6
7
8
9
10
def max_sub(lst):
    cur, res = 0, lst[0]
    for i in lst[1:]:
        if cur <= 0:
            cur = i
        else:
            cur += i
        if cur > res:
            res = cur
    return res

最关键的是移动 cur 使得 cur 时刻尽可能大。DP 的解法完全类似：

1
2
3
4
5
6
7
8
def max_sub(lst):
    dp = [lst[0]] + [0] * (len(lst) - 1)
    for i in range(1, len(lst)):
        if dp[i-1] <= 0:
            dp[i] = lst[i]
        else:
            dp[i] = lst[i] + dp[i-1]
    return max(dp)

具体实现和测试代码可参考：42_GreatestSumOfSubarrays

面试题 43：从 1 到 n 整数中 1 出现的次数

题目：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。例如输入 12，从 1 到 12 这些整数中包含 1 的数字有 1，10，11 和 12，1 一共出现了 5 次。

最简单的方法就是统计每个数中 1 的数量。给定数字怎么判断 1 的数量呢？可以用取余的方法：

1
2
3
4
5
6
7
def count_one(num):
    n = 0
    while num:
        if num % 10 == 1:
            n += 1
        num //= 10
    return n

不过这种方法显然不够高效，因为很明显大部分的数字是没有 1 的，或者只有少数的 1，书中介绍了一种很巧妙的方法，具体如下：

  • 将数字拆分为（1~ 去掉最高位的数字，去掉最高位的数字 ~ 给定数字）两段，也是方便使用递归（前面那段显然可以递归解决）。
  • 处理（去掉最高位的数字 ~ 给定数字）这一段，将第一个数字前面补 0，让两个数字位数一致。
    • 判断最高位是 1 的情况，分两种可能
      • 最高位大于 1，最高位是 1 的数量就是：10 ^（位数-1）
      • 最高位为 1，最高位是 1 的数量就是：给定数字 - 10 ^（位数-1）+ 1
    • 最高位固定后，其他位是 1 的情况，用排列组合的方法
      • 假设其中一个数字为 1，其他数字可以从 0-9 中选，也就是 10 种选法，总共 10 ^（位数-2）种
      • 考虑到一共有（位数 -1）个数字，总共（位数-1）× 10 ^（位数 - 2）种
      • 再考虑最高位的高度，总共 最高位 ×（位数-1）× 10 ^（位数 - 2）种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def count_one(num):
    lenth = int(len(str(num)))
    highest = int(str(num)[0])
    res_highest = 0
    # 0
    if highest == 0:
        return 0
    # 1-9 以内
    if lenth == 1 and highest > 0:
        return 1
    
    if lenth > 1 and highest > 1:
        res_highest = 10 ** (lenth - 1)
    elif lenth > 1 and highest == 1:
        res_highest = num - 10 ** (lenth - 1) + 1
    
    res_other = highest * (lenth - 1) * 10 ** (lenth - 2)
    res_recur = count_one(num % 10 ** (lenth - 1))
    
    return res_highest + res_other + res_recur

可以看出其中的关键是递归思维，当时看到这种思路真的是佩服不已，硬是把 O(kN) 的复杂度弄成 O(k)，思路非常精巧。

当然，还有一些其他思路，比如将每个数字 str 后 join 在一起，然后 count 1 的数量，代码也很简单。

1
2
3
def count_one(num):
    str_lst = map(str, range(1, num+1))
    return "".join(str_lst).count("1")

这种思路效率差不多是第一种思路的三倍。

具体实现和测试代码可参考：43_NumberOf1

面试题 44：数字序列中某一位的数字

题目：数字以 0123456789101112131415… 的格式序列化到一个字符序列中。在这个序列中，第 5 位（从 0 开始计数）是 5，第 13 位是 1，第 19 位是 4，等等。请写一个函数求任意位对应的数字。

Naive 的解法是循环数字的同时统计数字位数。稍微观察下，我们可以发现其实可以根据给定的位置确定数字是几位数，然后再找出那个数字。比如第 100 位，0-9 占了 10 位，到第 9 位（从 0 开始），10-99 一共 90×2=180 位，所以第 100 位自然就是从 10 开始的第 45 个数字（不包括 10），也就是 55 的第 1 位，也就是 5 啦。这里注意不要数错了，是从 0 开始计位的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def digit_at_index(index):
    if index < 10:
        return index
    num = 10
    i = 1
    while num < index:
        num += 9 * (10**i) * (i+1)
        i += 1
    num = 10
    for j in range(2, i):
        num += 9 * (10**j) * (j+1)
    num = 10**(i-1) + (index - num) // i
    index_from_left = index % i
    return int(str(num)[index_from_left])

重构一下：

1
2
3
4
5
6
7
8
9
10
11
12
def digit_at_index(index):
    if index < 10:
        return index
    num = 10
    i = 1
    while num < index:
        num += 9 * (10**i) * (i+1)
        i += 1
    need = num - 9 * (10**(i-1)) * i
    num = 10**(i-1) + (index - need) // i
    index_from_left = index % i
    return int(str(num)[index_from_left])

书中最后一步的计算方法比较 make sense，也很容易理解：

1
2
3
4
index_from_right = i - index % i
for j in range(1, index_from_right):
    num //= 10
return num % 10

具体实现和测试代码可参考：44_DigitsInSequence

面试题 45：把数组排成最小的数

题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组 {3, 32, 321}，则打印出这 3 个数字能排成的最小数字 321323。

这道题将展示 Zen 一样的 Python，先看这个特性：

1
2
3
4
from functools import cmp_to_key
lst = [123, 23, 12, 24, 3]
sorted(map(str, lst), key=cmp_to_key(lambda m, n: int(m+n)-int(n+m)))
# ['12', '123', '23', '24', '3']

这个返回的就是两两交换位置后从小到大的排列，比如：243 小于 324，所以 24 排在 3 前面。当然，你也可以加 reverse 字段让顺序反过来。于是 Pythonic 的解决方案就显而易见了：

1
2
3
def func(lst):
    return int("".join(sorted(map(str, lst), 
                              key=cmp_to_key(lambda m, n: int(m+n)-int(n+m)))))

如果非要按常规思路，第一步还是要得到上面输出的排序列表。这里可以根据每个数字的第一个数字先分组，因为最后整个的顺序整体一定是第一个数字小的在前面。但是组内只能老老实实排了，其思路类似选择排序，先找最小的，然后在剩下的里面继续找最小的，一直到列表为空为止。比如，随手写个（注意这里字符串比较和 int 规则一样，所以可以不转 int）：

1
2
3
4
5
6
7
8
def get_min(lst: List[str]):
    minx = lst[0]
    for i in lst[1:]:
        if (i+minx) < (minx+i):
            minx = i
    return minx
lst = [3, 35, 321, 3]
get_min(list(map(str, lst))) # "321"

求出来的 minx 可以放到一个新的列表，记得 count 下 lst 中该值的次数，有几次就在新列表中加几个。

具体实现（这个常规思路的版本没有）和测试代码可参考：45_SortArrayForMinNumber☆

面试题 46：把数字翻译成字符串

题目：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a”，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。例如 12258 有 5 种不同的翻译，它们分别是 “bccfi”、”bwfi”、”bczi”、”mcfi” 和”mzi”。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

可以用递归的思路分析问题，比如假设第一位转换（肯定可以），剩下的是一组；或者前两位（可能可以），剩下的一组。作者在书中提到，这种方法会有重复的子问题，然后从末尾开始倒着开始就可以消除这个问题。这里的原因不是特别理解，我觉得这个有点 DP 的意思，每两位不是一种就两种，然后沿着位置滑动，同时累加之前的记录即可，正着反着结果都一样。来个顺着的好了，反着的类似：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def translate_num_to_string(num: int):
    s = str(num)
    lenth = len(s)
    # 第一个肯定是 1
    counts = [1] + [0] * lenth
    for i in range(1, lenth+2):
        count = counts[i-1]
        if i < lenth + 1:
            d1 = int(s[i-2])
            d2 = int(s[i-1])
            if 10 <= d1 * 10 + d2 <= 25:
                count += counts[i-2]
            counts[i] = count
    return counts[-1]

如果有问题还请多多指正。反着的就不再赘述了。

具体实现和测试代码可参考：46_TranslateNumbersToStrings

面试题 47：礼物的最大价值

题目：在一个 m×n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？

一看就是个 DP 问题啦，因为每次只能向右或者向下，所以当前位置的最大值只能在左边或上边选，这样其实遍历的每一步都可以动态地把截止当前位置的最大值存下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def max_value(matrix):
    rows, cols = matrix.shape
    res = [0] * cols # 左上到右下
    for i in range(rows):
        for j in range(cols):
            left, up = 0, 0
            # 行确定时，最大值只能在左边（列上）
            if i > 0:
                up = res[j]
            # 列确定时，最大值只能在上边（行上）
            if j > 0:
                left = res[i]
            res[j] = max(up, left) + matrix[i][j]
    return res[-1]

当然，常规解法的 res 是一个二维矩阵，过程看起来会更加直观些。这里就不再赘述了。

具体实现和测试代码可参考：47_MaxValueOfGifts

面试题 48：最长不含重复字符的子字符串

题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含从 ‘a’ 到 ‘z’ 的字符。

又是一道 DP 题，好像类似这种往前滚动的（或者说有递推关系的？）都可以用 DP 来搞一搞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def max_not_duplicate_substring(s):
    lenth = len(s)
    dp = [1] + [0] * (lenth - 1)
    tmp = s[0]
    for i in range(1, lenth):
        if s[i] not in tmp:
            dp[i] = 1 + dp[i-1]
        else:
            # 找到重复的位置
            preindex = len(tmp) - tmp[::-1].index(s[i]) - 1
            # 重复字符之间的距离
            d = i - preindex
            # 如果重复字符之间的距离比上个长度小
            if d <= dp[i-1]:
                dp[i] = d
            # 否则就是上面的那个 if
        tmp.append(s[i])
    return max(dp)

特别需要注意的是，在找 s[i] 在 tmp 中的位置时，不能简单地用 tmp.index，因为这样会默认给出第一个位置，而我们要的是最后一个位置。当某个元素重复次数大于 2 时，就会有这个问题。

还有一种我觉得很巧妙的方法就是使用滑块，之前在做 LeetCode 时用过：Longest Substring Without Repeating Characters (LeetCode 3) | Yam，基本思想是维护一个滑块，遍历序列时，将不在滑块中的元素添加到滑块，同时计算长度；如果某个元素在滑块中，则从滑块中删除该元素。这里还有个需要注意的是，同时要维护两个指针 i 和 j，都从 0 开始，每添加一个元素到滑块，i 加 1；遇到之前出现过的元素，删除滑块中第 j（从 0 开始）个元素，j 加 1。

具体实现和测试代码可参考：48_LongestSubstringWithoutDup

面试题 49：丑数

题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。

Naive 的方法是对每个数依次除以 2 3 5，如果最后结果变成 1，就说明这个数是丑数。我们发现这里面有很多重复计算，比如 10 是丑数，100 肯定也是丑数（10 × 10），这时候其实不需要一个一个去除。于是我们就可以从 2 3 5 开始逐步往上乘，获得丑数序列。具体而言，假设有一个已经排好序的丑数序列（比如 2 3 5），我们把每个数分别乘以 2 3 和 5，找到第一个大于当前序列最大值（5）的数（分别是 6 6 10），然后在其中选出最小的就是（6）就是下一个丑数。而且进一步思考可以发现，实际上没必要每次都从最一开始乘，肯定有一个中间位置，左右数字分别乘了 2 3 或 5 后，正好在当前序列最大值的两侧，每次直接更新这个位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def ugly(n):
    lst = [1] + [0] * (n-1)
    loc2, loc3, loc5 = 0, 0, 0
    nxt = 1
    while nxt < n:
        lst[nxt] = min(lst[loc2]*2, lst[loc3]*3, lst[loc5]*5)
        # 把位置移到正好比下一个丑数小的地方
        while lst[loc2]*2 <= lst[nxt]:
            loc2 += 1
        while lst[loc3]*3 <= lst[nxt]:
            loc3 += 1
        while lst[loc5]*5 <= lst[nxt]:
            loc5 += 1
        
        nxt += 1
    return lst[-1]

具体实现和测试代码可参考：49_UglyNumber

面试题 50（一）：字符串中第一个只出现一次的字符

题目：在字符串中找出第一个只出现一次的字符。如输入”abaccdeff”，则输出 ‘b’。

这个题比较简单，遍历每个字符，同时将字符和出现次数存储为字典，然后再遍历一次字符串，如果次数为 1 时，对应的 key 就是要找的字符。这里唯一要注意的就是第二次遍历不是遍历字典（因为字典无序）。代码太简单就不赘述了，具体实现和测试代码可参考：50_01_FirstNotRepeatingChar。

另外，后面的三个相关题目挺有意思的，比如第二个用到了 ASCII 码作为下标，第三个的两个字符串分别创建字典和从字典中减次数。代码比较简单，这里不再赘述。

面试题 50（二）：字符流中第一个只出现一次的字符

题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 ‘g’。当从该字符流中读出前六个字符 “google” 时，第一个只出现一次的字符是 ‘l’。

这个和前面的类似，稍微变通一下就好。比如把进来的字符存到一个 list，这样第二轮遍历就是在这个 list 上做了。简单起见，这里假设读入的是字符，具体实现和测试代码可参考：50_02_FirstCharacterInStream。

面试题 51：数组中的逆序对

题目：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

说真的，这道题我是喜欢 Naive 的方法，比书中给出的第二个方法简单很多。具体做法是：依次遍历数字，每个数字和它后面的数字比，如果比它小，计数加 1，复杂度 O(N²）。但要想实现 O(NlogN) 的复杂度就只能用书中提供的方法了，它的思想比较简单：将统计过程和归并排序结合起来，即将数组分割成子数组，确定子数组中的逆序对数，同时排序。因为当子数组中只有两个元素时，很容易判断是否为逆序对。例子写起来比较麻烦，在《算法导论》中倒是看到一个比较容易理解的思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def count_inversions(lst, start, end):
    if start == end:
        return 0
    mid = (start + end) // 2
    left = count_inversions(lst, start, mid)
    right = count_inversions(lst, mid+1, end)
    count = merge_inversions(lst, start, mid, end)
    return left + right + count

def merge_inversions(lst, start, mid, end):
    left = lst[start: mid+1] + [math.inf]
    right = lst[mid+1:end+1] + [math.inf]
    i, j, count = 0, 0, 0
    for k in range(start, end+1):
        if left[i] <= right[j]:
            lst[k] = left[i]
            i += 1
        else:
            lst[k] = right[j]
            j += 1
            count += (mid + 1 - start) - i
    return count

可以看出整体是比较清晰的，就是在归并排序归并过程中统计逆序对的数量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def merge(lst, start, mid, end):
    left = lst[start: mid+1] + [math.inf]
    right = lst[mid+1:end+1] + [math.inf]
    i, j = 0, 0
    for k in range(start, end+1):
        if left[i] <= right[j]:
            lst[k] = left[i]
            i += 1
        else:
            lst[k] = right[j]
            j += 1
    return lst
def merge_sort(lst, start, end):
    if start == end:
        return 0
    mid = (start + end) // 2
    merge_sort(lst, start, mid)
    merge_sort(lst, mid+1, end)
    return merge(lst, start, mid, end)

更加 Pythonic 的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
def merge(left, right):
    result = []
    while left and right:
        result.append((left if left[0] <= right[0] else right).pop(0))
    return result + left + right

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)

此外还可以用树来实现，比如 BST 或 BIT，主要通过更新树的同时统计逆序对。

具体实现和测试代码可参考：51_InversePairs☆

面试题 52：两个链表的第一个公共节点

题目：输入两个链表，找出它们的第一个公共节点。

第一个公共节点意思是从该节点之后的节点都一样，如果可以从链表尾部开始遍历，问题就很简单了。所以可以先把两个链表放到两个栈里，然后依次弹出对比即可。书中还提到一个思路，类似于双指针，先让长链表移动两个链表长度差的步数，然后开始和短链表对比。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def find_first_common_node(link1, link2):
    len1 = get_length(link1)
    len2 = get_length(link2)
    if len1 > len2:
        long = link1
        short = link2
    else:
        long = link2
        short = link1
    for i in range(abs(len1-len2)):
        long = long.next
    while long and short and long.val != short.val:
        long = long.next
        short = short.next
    return long

如果链表可以存储长度，这种方法无疑是非常高效的。

具体实现和测试代码可参考：52_FirstCommonNodesInLists