本文共 2321 字，大约阅读时间需要 7 分钟。
为了高效合并两个有序数组，我们可以采用双指针技术。具体步骤如下：
i和j，分别指向两个数组的起始位置。A[i]小于等于B[j]，将A[i]加入结果数组，并移动i指针。B[j]加入结果数组，并移动j指针。示例代码如下：
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)
当需要合并多个有序列表时，可以使用堆队列（优先队列）算法。具体步骤如下：
value及其索引index。value添加到结果数组。示例代码如下：
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)
为了找到两个有序列表的中位数，我们可以采用递归分治的方法。具体步骤如下：
n： n为奇数，找到第n/2 + 1个元素作为中位数。n为偶数，找到第n/2和n/2 + 1个元素的平均值作为中位数。findKth函数来定位第k个元素： k-1个元素。findKth函数来找到中位数。示例代码如下：
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/