LeetCode88. 合并两个有序数组
题目说明
/**
*
* 给你两个有序整数数组 nums1 和 nums2,
* 请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
* <p>
* 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
* 你可以假设 nums1 的空间大小等于 m + n,
* 这样它就有足够的空间保存来自 nums2 的元素。
*
*/
思路分析
- 因为给定的数组是有序的,即按照升序排列的,假定数组1的长度为两数组长度之和,将合并后的元素存储到数组1中
- 可以使用逆向遍历法,即从数组的后边往前遍历,因为数组的后边元素更大,而且数组1后边的部分元素是空的,从后往前依次比较两个数组中元素的大小,将较大者依次存储数组1的后边
- 当某一数组中其他元素全部取完后,则直接从剩下的一个数组中取
- 源码见下
源码及分析
/**
*
* @param nums1 要合并的数组1
* @param m 数组1的长度
* @param nums2 要合并的数组2
* @param n 数组2的长度
*/
public void merge(int[] nums1, int m, int[] nums2, int n) {
//定义两个指针指向两个数组末尾,从后往前遍历,因为数组是有序的,即数组后边的元素大于前边的
int i = m - 1, j = n - 1;
//再定义指针k用于将数组中比较后较大的值依次放入数组末尾,cur记录当前的较大的数
int k = m + n - 1, cur = 0;
//循环扫描两个数组
while (i >= 0 || j >= 0) {
//如果第一个数组已经扫描完毕,则将第二个数组的所有元素全部放入num1
if (i == -1) {
cur = nums2[j];
j--;
//同理如果第二个数组扫描完毕
} else if (j == -1) {
cur = nums1[i];
i--;
//比较两个数组中末尾的元素大小,将大者先放入num1
} else if (nums1[i] > nums2[j]) {
cur = nums1[i];
i--;
} else {
cur = nums2[j];
j--;
}
//循环将较大者存入数组
nums1[k] = cur;
k--;
}
}