本文主要是介绍[leetcode-排序]--88. Merge Sorted Array,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Question 88. Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
中文: 给定两个有序的整型数组num1和num2,将num2合并进num1,成为一个新的数组。
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的空间足够大,完全可以把num2合并进num1。num1和num2初始化大小分别是m和n
解决思路:双指针法夹逼。因为num1和num2都是有序递增的,现在要把num2合并进num1,并且num1和num2的长度已知告诉我们了,这时候,如果我们从前往后比较,免不了要涉及到移动大量的数据,这是非常耗时间的,所以我们逆向思维,我们从后往前比较,然后从m+n-1 的位置开始存储(这么做有个前提,就是num1必须得确保有m+n-1这么大,本题目中,题目已经给定了。)。简单点说:就是从num1[m-1]和num2[n-1]开始比较,大的存储在最后,然后向前递推。
实现代码:
public void merge(int[] nums1, int m, int[] nums2, int n) {int index = m+n-1;//合并后最后一个元素的索引int ia = m-1;int ib = n-1;while(index >= 0){//num1已经遍历完了.将num2剩余数据存入num1中if(ia < 0){for(int i= ib; i>=0; i--){nums1[index--] = nums2[ib--];}return;}//num2已经遍历完了.将num1剩余数据存入num1中if(ib < 0){//其实什么都不用做,直接returnreturn;}//将较大的数字存储在最后.if(nums1[ia] > nums2[ib]){nums1[index--] = nums1[ia];ia--;}else {nums1[index--] = nums2[ib];ib--;}}
}
比较简单的代码,上面的代码唯一需要注意的是,要将ia和ib的判断放在循环的前面,否则就可能会出现当nums1或则nums2本身为空数组时,出现数组越界的异常。
这个代码一次提交就Accept了。
这篇关于[leetcode-排序]--88. Merge Sorted Array的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!