[数据结构与算法] 合并两个有序数组

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 合并两个有序数组 -> 正文阅读

[数据结构与算法]合并两个有序数组

题目链接

思路

双指针反向排序(从大到小);
如果从小到大需要定义一个临时数组避免覆盖掉num1中的元素
初始化idx1和idx2和sumLen;定义cur
开始循环;结束条件idx1和idx2都小于0
每次从两个数组的尾部取出较大的数字放置到nums1最后面;直至循环结束

java

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int idx1 = m - 1;
    int idx2 = n - 1;
    int sumLen = m + n - 1;
    int cur;
    while (idx1 >= 0 || idx2 >= 0) {
        if (idx1 == -1) {
            cur = nums2[idx2--];
        } else if (idx2 == -1) {
            cur = nums1[idx1--];
        } else if (nums1[idx1] > nums2[idx2]) {
            cur = nums1[idx1--];
        } else {
            cur = nums2[idx2--];
        }
        nums1[sumLen--] = cur;
    }
}

go

func merge(nums1 []int, m int, nums2 []int, n int) {
    idx1, idx2, sumLen := m-1, n-1, m+n-1
    var cur int
    for idx1 >= 0 || idx2 >= 0 {
        if idx1 == -1 {
            cur = nums2[idx2]
            idx2--
        }else if idx2 == -1 {
            cur = nums1[idx1]
            idx1--
        }else if nums1[idx1] > nums2[idx2] {
            cur = nums1[idx1]
            idx1--
        }else {
            cur = nums2[idx2]
            idx2--
        }
        nums1[sumLen] = cur
        sumLen--
    }
}