# 算法


## 合并两个有序数组

> 给你两个按 非递减顺序 排列的整数数组 `nums1` 和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `nums2`
> 中的元素数目。  
> 请你 合并 `nums2` 到 `nums1` 中，使合并后的数组同样按 非递减顺序 排列。  
> **注意**：最终，合并后数组不应由函数返回，而是存储在数组 `nums1` 中。为了应对这种情况，`nums1` 的初始长度为 `m + n`
> ，其中前 `m` 个元素表示应合并的元素，后 `n` 个元素为 `0` ，应忽略。`nums2` 的长度为 `n` 。

```java
// 倒序双指针
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx = m + n - 1, idx1 = m - 1, idx2 = n - 1;
        while (idx1 >= 0 && idx2 >= 0) {
            if (nums1[idx1] > nums2[idx2]) {
                nums1[idx--] = nums1[idx1--];
            } else {
                nums1[idx--] = nums2[idx2--];
            }
        }

        while (idx2 >= 0) {
            nums1[idx--] = nums2[idx2--];
        }
    }
}

// 正序双指针
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] res = new int[m + n];
        int idx = 0, idx1 = 0, idx2 = 0;

        while (idx1 < m && idx2 < n) {
            if (nums1[idx1] < nums2[idx2]) {
                res[idx++] = nums1[idx1++];
            } else {
                res[idx++] = nums2[idx2++];
            }
        }

        while (idx1 < m) {
            res[idx++] = nums1[idx1++];
        }

        while (idx2 < n) {
            res[idx++] = nums2[idx2++];
        }
        for (int i = 0; i < res.length; i++) {
            nums1[i] = res[i];
        }
    }
}
```