LeetCode：MergeArray(合并有序数组)-蒲公英云

LeetCode：MergeArray(合并有序数组)

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

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

相关文章：

LeetCode：55. Jump Game（跳远比赛）
Leetcode：300. Longest Increasing Subsequence（最大增长序列）
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