双指针 (Two Pointers)

双指针（Two Pointers）是一种常用的算法思想，它通常用于在数组或链表中寻找一些特定的性质或解决一些特定的问题。 双指针算法的基本思想是，定义两个指针，分别指向数组或链表中的不同位置，然后根据问题的特性， 移动指针来达到解决问题的目的。

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

重点：nums1和nums2已经被排序

Java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 方法二：双指针（利用两个数组有序特性，把两个数据看成队列，使用双指针方法

        int p1 = 0, p2 =0;
        int[] sorted = new int[m +n];
        // current 当前值
        int cur;
        while (p1 < m || p2 < n) {
            // nums1中的有序元素已经全部被遍历完，只能取nums2中的元素，例如nums1 = []
            if (p1 == m ) {
                cur = nums2[p2++];
            // 同上
            } else if (p2 == n) {
                cur = nums1[p1++];
            // 如果以上两种情况都不满足，则比较nums1[p1]和nums2[p2]的大小
            } else if (nums1[p1] < nums2[p2]) {
                // 将较小的元素赋值给cur变量，并将对应的指针p1或p2加1
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            // 最后将cur赋值给sorted[p1+p2-1]，即将cur放入合并后的有序数组中
            sorted[p1 + p2 - 1] = cur;
        }
        // 最后合并（保存）到 nums1 中
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}

Python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        sorted = []
        p1, p2 = 0, 0
        while p1 < m or p2 < n:
            if p1 == m:
                sorted.append(nums2[p2])
                p2 += 1
            elif p2 == n:
                sorted.append(nums1[p1])
                p1 += 1
            elif nums1[p1] < nums2[p2]:
                sorted.append(nums1[p1])
                p1 += 1
            else:
                sorted.append(nums2[p2])
                p2 += 1
        nums1[:] = sorted