目录

算法

gongyho 收录于笔记

2024-09-24 约 390 字预计阅读 1 分钟

目录

合并两个有序数组

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


// 倒序双指针
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];
        }
    }
}