题目
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.
Example:
```plain text Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
**Constraints**:
- 10^9 <= nums1[i], nums2[i] <= 10^9
nums1.length == m + n
nums2.length == n
**题目大意**
```plain text
合并两个已经有序的数组，结果放在第一个数组中，第一个数组假设空间足够大。要求算法时间复杂度
足够低。
解题思路
为了不大量移动元素，就要从2个数组⻓度之和的最后一个位置开始，依次选取两个数组中大的数，从第一个数组的尾巴开始往头放，只要循环一次以后，就生成了合并以后的数组了。
代码
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
# two get pointers for nums1 and nums2
p1 = m - 1
p2 = n - 1
# set pointer for nums1
p = m + n - 1
# while there are still elements to compare
while p1 >= 0 and p2 >= 0:
if nums1[p1] < nums2[p2]:
nums1[p] = nums2[p2]
p2 -= 1
else:
nums1[p] = nums1[p1]
p1 -= 1
p -= 1
# add missing elements from nums2
nums1[:p2 + 1] = nums2[:p2 + 1]
给定K个有序数组，每个数组有n个元素，想把这些数组合并成一个有序数组
可以利用最小堆完成，时间复杂度是O(nklogk)，具体过程如下：
创建一个大小为nk的数组保存最后的结果，创建一个大小为k的最小堆，堆中元素为k个数组中的每个数组的第一个元素重复下列步骤nk次：
每次从堆中取出最小元素（堆顶元素），并将其存入输出数组中。用堆顶元素所在数组的下一元素将堆顶元素替换掉，如果数组中元素被取光了，将堆顶元素替换为无穷大。每次替换堆顶元素后，重新调整堆初始化最小堆的时间复杂度O（k），总共有kn次循环，每次循环调整最小堆的时间复杂度是O（logk），所以总的时间复杂度是O（knlogk）
import sys
class HeapNode:
def __init__(self,x,y=0,z=0):
self.value=x
self.i=y
self.j=z
def Min_Heap(heap):#构造一个堆，将堆中所有数据重新排序
HeapSize = len(heap)#将堆的长度单独拿出来方便
for i in range((HeapSize -2)//2,-1,-1):#从后往前出数
Min_Heapify(heap,i)
def Min_Heapify(heap,root):
heapsize=len(heap)
MIN=root
left=2*root+1
right=left+1
if left<heapsize and heap[MIN].value>heap[left].value:
MIN=left
if right <heapsize and heap[MIN].value>heap[right].value:
MIN=right
if MIN!=root:
heap[MIN], heap[root] = heap[root], heap[MIN]
Min_Heapify(heap, MIN)
def MergeKArray(nums,n):
# 合并k个有序数组，每个数组长度都为k
knums=[]
output=[]
for i in range(len(nums)):
subnums=nums[i]
knums.append(HeapNode(subnums[0],i,1))
#k个元素初始化最小堆
Min_Heap(knums)
for i in range(len(nums)*n):
# 取堆顶，存结果
root=knums[0]
output.append(root.value)
#替换堆顶
if root.j<n:
root.value=nums[root.i][root.j]
root.j+=1
else:
root.value=sys.maxsize
knums[0]=root
Min_Heapify(knums,0)
return output
knums=[[1,2,3],[1,3,6],[4,5,8]]
print(MergeKArray(knums,3))