LeetCode第88题合并两个有序数组

简介: 文章分享了LeetCode第88题"合并两个有序数组"的解法,通过从后向前的合并策略避免了数组元素的前移,使用三个指针高效地完成了合并过程。

继续打卡算法题,今天学习的是第88题合并两个有序数组,这道题目是道简单题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。

image.png

分析一波题目

本题需要将两个数组合并结果存入第一个数组,我们如果从前往后合,需要移动数据。我们可以从最大的数开始合并,将大的数填充第一个数组的后面,这样就不需要移动第一个数组的数据了。

image.png

本题解题技巧

1、使用三个指针,一个是index1最开始指向数组1最后一个元素,一个是index2指向数组2最后一个元素,一个指针指向数组1最后一个位置(表示下一次需要存的数)

编码解决

class Solution {
   
   
    public void merge(int[] nums1, int m, int[] nums2, int n) {
   
   

        int newSize = m+n;
        int startIndex = m+n -1;

        int index1 = m-1;
        int index2= n-1;

        while (index1 >=0 || index2 >= 0) {
   
   

            if(index1 >= 0 && index2>=0) {
   
   
                  int t1 = nums1[index1];
                  int t2 = nums2[index2];
                  if(t1 >= t2) {
   
   
                    nums1[startIndex] = t1;
                    index1--;
                  } else {
   
   
                    nums1[startIndex] = t2;
                    index2--;
                  }
            } else if(index1 >=0){
   
   
                    int t1 = nums1[index1];
                    nums1[startIndex] = t1;
                    index1--;
            } else if(index2 >=0) {
   
   
                    int t2 = nums2[index2];
                    nums1[startIndex] = t2;
                    index2--;

            }
            startIndex--;

        }

    }
}

总结

1、本题解题是从最大的数开始合并,避免了移动数组元素

相关文章
|
5月前
|
Go 索引 Perl
【LeetCode 热题100】【二叉树构造题精讲:前序 + 中序建树 & 有序数组构造 BST】(详细解析)(Go语言版)
本文详细解析了二叉树构造的两类经典问题:通过前序与中序遍历重建二叉树(LeetCode 105),以及将有序数组转化为平衡二叉搜索树(BST,LeetCode 108)。文章从核心思路、递归解法到实现细节逐一拆解,强调通过索引控制子树范围以优化性能,并对比两题的不同构造逻辑。最后总结通用构造套路,提供进阶思考方向,帮助彻底掌握二叉树构造类题目。
277 9
|
11月前
leetCode(删除有序数组中的重复项)
如何在不使用额外空间的情况下,通过双指针法原地删除有序数组中的重复项。
95 2
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
LeetCode第26题删除有序数组中的重复项
这篇文章介绍了LeetCode第26题"删除有序数组中的重复项"的解题方法,通过使用双指针技巧,高效地去除数组中的相邻重复元素。
LeetCode第26题删除有序数组中的重复项
LeetCode第80题删除有序数组中的重复项 II
文章介绍了LeetCode第80题"删除有序数组中的重复项 II"的解法,利用双指针技术在O(1)空间复杂度内原地删除重复元素,并总结了双指针技术在处理有序数组问题中的应用。
LeetCode第80题删除有序数组中的重复项 II
|
Python
【Leetcode刷题Python】977. 有序数组的平方
解决LeetCode "有序数组的平方" 问题的方法:使用Python内置的快速排序、直接插入排序(但会超时)和双指针技术,并给出了每种方法的Python实现代码。
66 1
【Leetcode刷题Python】977. 有序数组的平方
|
11月前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
101 0
|
Python
【Leetcode刷题Python】108. 将有序数组转换为二叉搜索树
LeetCode上108号问题"将有序数组转换为二叉搜索树"的Python实现,通过递归选取数组中间值作为根节点,构建高度平衡的二叉搜索树。
89 2
|
算法 测试技术 程序员
力扣经典150题第二十七题:两数之和 II - 输入有序数组
力扣经典150题第二十七题:两数之和 II - 输入有序数组
89 1
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
140 0