本文共 2321 字，大约阅读时间需要 7 分钟。

合并两个有序数组

为了高效合并两个有序数组，我们可以采用双指针技术。具体步骤如下：

示例代码如下：

def mergeList(A, B):    s1 = len(A)    s2 = len(B)    i, j = 0, 0    res = []    while i < s1 and j < s2:        if A[i] <= B[j]:            res.append(A[i])            i += 1        else:            res.append(B[j])            j += 1    res += A[i+1:] + B[j+1:]    return res

测试示例：

A = [1,2,5,7,9]B = [2,4,6,8,10,11,34,55]res = mergeList(A, B)print(res)

合并多个有序列表

当需要合并多个有序列表时，可以使用堆队列（优先队列）算法。具体步骤如下：

示例代码如下：

def mergeMultiList(lists):    import heapq    from collections import deque    lists = list(map(lambda x: deque(x), lists))    pq = []    for ind, val in enumerate(lists):        heapq.heappush(pq, (val, ind))    res = []    while pq:        value, index = heapq.heappop(pq)        res.append(value)        if lists[index]:            heapq.heappush(pq, (lists[index].popleft(), index))    return res

测试示例：

lists = [[1,2,5,7,9], [2,4,6,8,10,11,34,55], [1,3,5,8,10,15]]res = mergeMultiList(lists)print(res)

寻找两个有序列表中的中位数

为了找到两个有序列表的中位数，我们可以采用递归分治的方法。具体步骤如下：

示例代码如下：

class Solution:    def findMedianSortedArrays(self, A, B):        n = len(A) + len(B)        if n % 2 == 1:            return self.findKth(A, B, n // 2 + 1)        else:            smaller = self.findKth(A, B, n // 2)            bigger = self.findKth(A, B, n // 2 + 1)            return (smaller + bigger) / 2.0    def findKth(self, A, B, k):        if len(A) == 0:            return B[k-1]        if len(B) == 0:            return A[k-1]        if k == 1:            return min(A[0], B[0])        a = A[k//2 - 1] if len(A) >= k//2 else None        b = B[k//2 - 1] if len(B) >= k//2 else None        if b is None or (a is not None and a < b):            return self.findKth(A[k//2:], B, k - k//2)        return self.findKth(A, B[k//2:], k - k//2)

测试示例：

s = Solution()print(s.findMedianSortedArrays([1, 2, 3, 4, 5, 6], [2, 3, 4, 5]))

转载地址：http://zfpbz.baihongyu.com/