package DataStructure.array;

/**
 * 88. 合并两个有序数组 https://leetcode.cn/problems/merge-sorted-array
 * 题目简述:将一个有效长度为m(实际容量m+n)的非递减数组nums1和一个有效长度为n的数组nums2并为一个非递减数组,结果存储在nums1中
 */
public class Merge {

 /**
 * 思路:双指针,p1指向num1的有效末尾,p2指向nums2的有效末尾,逐次比较选取较大的数字从实际末尾从后往前填充nums1
 * 最后若p1扫描完了p2还未扫描完,则直接将nums2剩余元素依次填充到nums1剩余位置
 */
 public void merge(int[] nums1, int m, int[] nums2, int n) {
 int i=m+n-1, p1=m-1, p2=n-1;
 while(p1 >=0 && p2 >= 0) {
 if(nums1[p1] > nums2[p2]) {
 nums1[i--] = nums1[p1--];
 } else {
 nums1[i--] = nums2[p2--];
 }
 }
 while(p2 >= 0) {
 nums1[i--] = nums2[p2--];
 }
 }
}