【CT】LeetCode手撕—88. 合并两个有序数组

题目

• 原题连接：88. 合并两个有序数组

---

1- 思路

模式识别

• 模式1：两个有序数组合并 ——> 双指针
• 模式2：返回结果填充到 nums1[m+n] ——> 需要开辟新的数组空间 sorted[m+n] 最后结果赋值给 nums1

思路

• 1.定义双指针：分别指向 nums1 和 nums2
• 2.开辟新的数组空间：sorted[m+n] ，在合并完之后赋值

---

2- 实现

⭐88. 合并两个有序数组——题解思路

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int[] sorted = new int[m+n];int si = 0;int index1=0,index2=0;while(index1<m && index2<n){if(nums1[index1]<=nums2[index2]){sorted[si++] = nums1[index1++];}else{sorted[si++] = nums2[index2++];}}while(index1<m){sorted[si++] = nums1[index1++];}while(index2<n){sorted[si++] = nums2[index2++];}// 赋值给 nums1for(int i = 0 ; i < m+n;i++){nums1[i] = sorted[i];}}
}

---

2- ACM实现

public class mergeTwoArrays {public static int[] mergeTwoArrays(int[] nums1,int m, int[] nums2,int n){int index1 = 0,index2 = 0;int si = 0;int[] sorted = new int[m+n];while(index1<m && index2<n){if(nums1[index1]<=nums2[index2]){sorted[si++] = nums1[index1++];}else{sorted[si++] = nums2[index2++];}}while(index1<m){sorted[si++] = nums1[index1++];}while(index2<n){sorted[si++] = nums2[index2++];}for(int i = 0 ; i < m+n;i++){nums1[i] = sorted[i];}return nums1;}public static void main(String[] args) {System.out.println("输入数组1和数组2长度 m 和 n");Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[] nums1 = new int[m+n];int[] nums2 = new int[n];System.out.println("输入数组1");for(int i = 0 ; i <m;i++){nums1[i] = sc.nextInt();}System.out.println("输入数组2");for(int j = 0 ; j < n;j++){nums2[j] = sc.nextInt();}int[] res = mergeTwoArrays(nums1,m,nums2,n);for(int r:res){System.out.print(r+" ");}}
}