LeetCode面试题10.01.SortedMergeLCCI【Easy】【Python】【双指针】问题LeetCode给定两个排序数组A和B，其中A的末尾有足够的缓冲空间给B。编写一个将B合并到A中并对其进行排序的方法。分别用m和n个元素初始化A和B。示例：输入：A=[1,2,3,0,0,0]，m=3B=[2,5,6]，n=3输出：[1,2,2,3,5,6]思路解一对指针指针i指向A[m-1]，指针j指向B[n-1]。A[i]与B[j]比较，取较大的值插入A的末尾，i和j指针分别向前移动。如果i指针已经移到A的头部，判断如果B还有元素，则直接插入到A的前面。时间复杂度：O(m+n)空间复杂度：O(1)Python3代码类解决方案：defmerge(self,A:List[int],m:int,B:List[int],n:int)->None:"""不返回任何东西，而是就地修改A。"""#解决方案一：排序#A[m:]=B#A.sort()#解决方案二：两点ifn==0:#B=[]返回i,j,k=m-1,n-1,m+n-1whilei>-1andj>-1:#>-1,ifm=0orn=0，则i=-1或j=-1如果A[i]<=B[j]：A[k]=B[j]k-=1j-=1否则：A[k]=A[i]k-=1i-=1ifj>-1:A[:j+1]=B[:j+1]#A=[],B=[1]解决方案2对B排序并插入AtA的结尾，使用sort函数进行排序。时间复杂度：O((m+n)log(m+n))空间复杂度：O(log(m+n))Python3代码类解决方案：defmerge(self,A:List[int],m:int,B:List[int],n:int)->None:"""不返回任何东西，就地修改A。"""#解决方案一：sortA[m:]=BA.sort()代码地址GitHub链接相关话题LeetCode0088.MergeSortedArrayMergetwoorderedarrays
