package point;

/**
 * 题目:合并两个有序的数组,合并的数组能够容下两个数组的长度
 * y: 1 4 _ _
 * 2 3
 * 合并结果: 1 2 3 4
 * @Author Gavin
 * @date 2021年12月19日 22:00
 */
public class array_1 {
 /**
 * 解题思路:使用两个指针依次循环对比两个数组下标的值
 * 需要注意的是如果按照正序来比较的话一旦设置值的时候可能导致数组后面元素的移动,
 * 这样时间复杂度就很高了,所以我们考虑用逆序的方式进行比较,先从数组大的元素开始比较
 * 因为数组是递增的,所以最大的元素放到最后就行,这样就不会造城数组元素的移动
 */
 //Time:O(m+n) Space:O(1)
 public static int[] solution(int[] num1,int[] num2,int m,int n){
 int i=m-1,j=n-1,k=m+n-1;
 while (i>=0&&j>=0){
 if(num1[i]>num2[j]){
 num1[k--]=num1[i--];
 }else{
 num1[k--]=num2[j--];
 }
 }
 while (j>=0)num1[k--]=num2[j--];
 return num1;
 }
}