LeetCode：MergeArray(合并有序数组)

电玩女神 2022-04-15 05:05 178阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：

python实现方式1:

源码地址：

--------------------

### 题目描述： ###

比如两个数组：int \[\] arr1=\{1,2,3,4\}; int \[\] arr2=\{4,5,6,7,8\};

--------------------

### java实现方法1： ###

也是比较常用的一种，两个指针；

步骤：

1.两个指针分别指向数组的起始位置；

2.比较他们两个指向的值，如果小的放进另外一个数组，进行比较；

3.再判断两个数组是否都遍历完；

/**
         * 按照要求合并两个数组
         *
         * @param arr1 数组1
         * @param arr2 数组2
         */
        private int[] merge(int[] arr1, int[] arr2) {
            if (arr1 == null || arr1.length == 0) {
                return arr2;
            }
            if (arr2 == null || arr2.length == 0) {
                return arr1;
            }
            int i = 0;
            int j = 0;
            int[] newArr = new int[arr1.length + arr2.length];
            int count = 0;
            while (i < arr1.length && j < arr2.length) {
                if (arr1[i] < arr2[j]) {
                    newArr[count] = arr1[i];
                    i++;
                    count++;
                }else if (arr1[i] == arr2[j]) {
                    newArr[count] = arr1[i];
                    i++;
                    j++;
                    count++;
                }else{
                    newArr[count] = arr2[j];
                    j++;
                    count++;
                }
                // 当arr1的指针已经到了末尾,直接把arr2后面的数组添加到数组中
                if (i  == arr1.length) {
                    for (int index = j; index < arr2.length; index++) {
                        newArr[count] = arr2[index];
                        count++;
                    }
                }
    
                // 当arr2的指针已经为到末尾，直接将arr1中的数组添加到数组当中
                if (j == arr2.length) {
                    for (int index = i; index < arr1.length; index++) {
                        newArr[count] = arr1[index];
                        count++;
                    }
                }
            }
            return Arrays.copyOfRange(newArr, 0, count);
        }

时间复杂度：O(n+m)

空间复杂度：O(n)

--------------------

### python实现方式1: ###

def merge(self, nums1: List[int], nums2: List[int]) -> List[int]:
            '''
                合并两个数组
            Args:
                nums1:数组1
                nums2:数组2
            Returns:
                合并后数组
            '''
            if not nums1:
                return nums2
            if not nums2:
                return nums1
            i, j, result = 0, 0, []
            while i < len(nums1) and j < len(nums2):
                if nums1[i] < nums2[j]:
                    result.append(nums1[i])
                    i += 1
                elif nums1[i] == nums2[j]:
                    result.append(nums1[i])
                    i += 1
                    j += 1
                else:
                    result.append(nums2[j])
                    j += 1
            if i == len(nums1):
                result.extend(nums2[j:len(nums2)])
            if j == len(nums2):
                result.extend(nums1[i:len(nums1)])
            return result

时间复杂度：O(n+m)

空间复杂度：O(n)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode