LeetCode Merge Sorted Array

LeetCode Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.


把两个已排序数组合并成一个有序数组。注意是保存到nums1中。我一开始理解的是在合并过程中不能借助额外空间,所以用两个指针i,j指向两个数组,然后每次从nums2中找第一个小于nums1[i]的数,然后交换nums1[i]和nums2[j],再调整nums2使有序。如此下去,nums1就是合并有序数组中的较小数组部分。

这个版本的完整代码如下:

class Solution {
public:
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		if (n == 0)return;
		int i = 0;
		while (i < m) {
			int j = 0;
			while (nums1[i] <= nums2[j] && i < m)i++;
			if (i >= m)break;
			swap(nums1[i], nums2[j]);
			while (j<n - 1 && nums2[j]>nums2[j + 1]) {
				swap(nums2[j], nums2[j + 1]);
				j++;
			}
			i++;
		}
		for (int j = 0; j < n; j++) {
			nums1[i++] = nums2[j];
		}
	}
};

本代码提交AC,用时6MS。

但是只击败了15%的人,仔细看看算法实现,最坏复杂度是O(n*m),因为如果nums1={6,7,8,9,10},nums2={1,2,3,4,5},则nums1[i]每和nums2[0]交换一次,nums2调整时都要交换n-1次,所以最坏复杂度是O(n*m)。所以应该还有更好的算法。

看题解,发现我没有很好利用nums1的数组大小至少是n+m这个信息,这说明合并之后的整个数组,最大下标只能是n+m-1,所以我们可以对nums1和nums2从后往前比较,把更大的元素依次在nums1[n+m-1]往前放,这样共3个指针,他们之间不会有overlap。此算法的复杂度只有O(max(n,m))

完整代码如下:

class Solution {
public:
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		if (n == 0)return;
		int i = m - 1, j = n - 1, k = m + n - 1;
		while (i >= 0 || j >= 0) {
			int a = i >= 0 ? nums1[i] : INT_MIN;
			int b = j >= 0 ? nums2[j] : INT_MIN;
			if (a > b) {
				nums1[k--] = a;
				i--;
			}
			else {
				nums1[k--] = b;
				j--;
			}
		}
	}
};

本代码提交AC,用时3MS,果然快多了。

Leave a Reply

Your email address will not be published. Required fields are marked *