LeetCode 面试经典150题之合并两个有序数组

LeetCode 面试经典150题之合并两个有序数组

一、题目

1.题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

2.题目分析：

本题是一个原地排序题，可以采用两种策略：一种是先将数组2插入数组1，再进行排序；另一种是再插入的时候就进行比较，让数组2插入的每个数字都在正确的位置。
下面将介绍四种方法。

二、具体方法

1.调用函数，快速实现排序

nums1[m:]=nums2 nums1.sort()

这种方法通过调用sort函数，自动的实现排序。但是本题要考察的就是排序，因此，比太建议采用这种方法。但是在现实操作场景中，这种方法能够快速达到目标。

2.双指针排序法

nums1[m:m+n]=nums2 left=0right=mwhileleft<=right<m+n:ifnums1[left]>nums1[right]:temp=nums1[right]nums1[left+1:right+1]=nums1[left:right]nums1[left]=temp left+=1right+=1else:left+=1

首先，我们需要跟前面一样，先将数组2整个并入到数组1当中，再通过一个左指针，一个右指针分别来指向原本为数组1中的数和原本来自数组2中的数。如果右指针的数比左指针的小，那就需要将左指针当先指向及右指针当前指向之前的数整体往后移动一个单位，再将当前有指针指向的数，放入左指针当前指向的位置。最后右指针和左指针都要往后移动一个单位。后面重复这个操作。

3.冒泡排序法

nums1[m:m+n]=nums2foriinrange(m+n-1):forjinrange(m+n-1-i):ifnums1[j]>nums1[j+1]:temp=nums1[j]nums1[j]=nums1[j+1]nums1[j+1]=temp

冒泡排序法，同样是先将两个数组合并，再根据冒泡排序算法的基本步骤，完成后面的排序。这里简要介绍冒泡排序的基本思想：先从头到尾遍历这个数组，每次找到相邻的两个数，如果前面的数比后面的数大，那就将前后的数调换位置。然后再比较刚才比较的第二个数和它的后面的数的大小 ，重复这个操作。一直比较到最后一个数。这样我们每次都将大的数往后移动，最后一次循环后，最大的数就到了最后面。那么这个数组的最后一个已经确定了，我们可以将它看作大小为原来减1的要排序数组。重复上一个循环的操作。直至所有的数都排好序。

需要注意的冒泡排序的循环的参数。在外层循环里面，我们需要对大小为N的数组进行排序，那么只需要对N-1个数进行排序就行，也就是说外层循环只需要执行N-1次。对于内层循环，因为我们每次排序都是从第一个开始的，并且每进行一次外层循环，数组的后面位置确定的数就增加1个，因此，内层循环进行N-i次即可。

4.双指针插入排序

i=0j=0whilej<n:ifi<(j+m):ifnums1[i]<=nums2[j]:i+=1else:forkinrange(m+j-1,i-1,-1):nums1[k+1]=nums1[k]nums1[i]=nums2[j]i+=1j+=1else:nums1[i]=nums2[j]j+=1i+=1

这个方法是在插入的时候就将数组2中的数，放入其正确的位置。这里循环结束的条件是数组2里面的数全部都插入完毕，即j >=n。只有当指针i当前指向的是数组1的有效数字的时候，才需要对两个数组当前所指的数的大小进行判断。数组1的有效范围原本为m但是由于每插入一个数组2中的数，其有效长度都会+1，因此当插入j个数组2中的数的时候，其有效长度就变为j+m了。如果数组1当前所指的数小于等于数组2中当前被指的数，那么是不需要插入的，指针i直接往后移动一个单位。如果指针i当前所指的数组1中的数是大于指针j当前所指的数组2中的数，那么我们要先把i当前所指的位置，及其之后的有效数字都往后移动一个，然后将j所指的数，插入i当前所指的位置。并且由于j所指的数已经插入，因此j需要往后移动，而i所指的是刚插入的数，因此也要往后移动一个。然后继续进行比较。直至数组1中的所有有效数字都被比较完毕，但是数组2中还有数没插入时，直接将数组2中剩下的数插入即可。