【LeetCode】手撕系列—88. 合并两个有序数组_双指针

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

1- 思路

定义三个指针 p1、p2 以及 cur；其中 p1 用于遍历 nums1；p2用于遍历 nums2；cur 为判断当前存储的元素
定义一个 sorted 数组长度为 (m+1)，存储合并后的数组

• 四个判断
  • if( p1 == m)：此时表明，nums1中的数据已经存储完，则 cur = nums2[p2++]
  • if( p2 == n)：此时表明，nums2中的数据已经存储完，则 cur = nums1[p1++]
  • if(nums1[p1] < nums2[p2])：则 cur = nums1[p1++]
  • 剩余最后一个条件 cur = nums2[p2++]
• 收集结果

2- 题解

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

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1=0 , p2=0;
        int[] sorted = new int[m+n];

        int cur;
        while(p1<m || p2<n){
            if(p1 == m){
                cur = nums2[p2++];
            }else if(p2 == n){
                cur = nums1[p1++];
            }else if(nums1[p1] < nums2[p2]){
                cur = nums1[p1++];
            }else{
                cur = nums2[p2++];
            }
            sorted[p1+p2-1] = cur;
        }

        for(int i = 0 ; i != m+n;i++){
            nums1[i] = sorted[i];
        }
    }
}

3- ACM模式

public class merge {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1=0 , p2=0;
        int[] sorted = new int[m+n];

        int cur;
        while(p1<m || p2<n){
            if(p1 == m){
                cur = nums2[p2++];
            }else if(p2 == n){
                cur = nums1[p1++];
            }else if(nums1[p1] < nums2[p2]){
                cur = nums1[p1++];
            }else{
                cur = nums2[p2++];
            }
            sorted[p1+p2-1] = cur;
        }

        for(int i = 0 ; i != m+n;i++){
            nums1[i] = sorted[i];
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        scanner.nextLine(); // Consume newline left-over

        int[] nums1 = new int[m + n]; // Assuming nums1 has enough space to hold additional elements from nums2
        int[] nums2 = new int[n];

        // Reading nums1 elements
        for (int i = 0; i < m; i++) {
            nums1[i] = scanner.nextInt();
        }
        scanner.nextLine(); // Consume newline left-over

        // Reading nums2 elements
        for (int i = 0; i < n; i++) {
            nums2[i] = scanner.nextInt();
        }

        merge(nums1, m, nums2, n);

        // Output the merged array
        for (int i = 0; i < m + n; i++) {
            System.out.print(nums1[i] + " ");
        }
    }
}