原题链接:
https://leetcode.cn/problems/merge-sorted-array/

解法1: 双指针

最优解

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

/** 
    双指针
    初始化三个指针
    p1 = m - 1 , p2 = n - 1
    p = m + n - 1
    核心思想就是从后往前进行合并 
    因为nums1后面的位置是空的 一个极端的情况 如果nums1中所有元素都比nums2大
    那么就是将nums1中所有元素都移动到后面 而此时相当于nums1前面的位置都空出来了 直接填入nums2即可 不需要考虑覆盖问题
*/
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m + n - 1;
        int p1 = m - 1;
        int p2 = n - 1;

        // 如果p2还有要合并元素则参加循环
        while(p2 >= 0){
            if(p1 >= 0 && nums1[p1] > nums2[p2]){
                nums1[p--] = nums1[p1--];
            }else{
                // 如果p1 < 0 证明所有nums1中元素都已经挪到了后面 
                // 剩下就是移动nums2内的元素就完事了
                nums1[p--] = nums2[p2--];
            }
        }
    }
}

解法2: 堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        PriorityQueue<Integer>pq = new PriorityQueue<>((o1,o2)->o1 - o2);
        
        for(int i = 0 ; i < m ; i++){
            pq.add(nums1[i]);
        }

        for(int i = 0 ; i < n ; i++){
            pq.add(nums2[i]);
        }
        
        for(int i = 0 ; i < m + n ; i++){
            nums1[i] = pq.poll();
        }

    }
}