首页 > 其他分享 >力扣递归之88. 合并两个有序数组

力扣递归之88. 合并两个有序数组

时间:2024-02-08 22:56:20浏览次数:29  
标签:递归 int 元素 合并 力扣 88 数组 nums1 nums2

给你两个按 非递减顺序 排列的整数数组 nums1nums2,另有两个整数 mn ,分别表示 nums1nums2 中的元素数目。

请你 合并 nums2nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n

 

示例 1:

输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。

示例 2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3:

输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
从后往前赋值
class Solution {     public void merge(int[] nums1, int m, int[] nums2, int n) {         mergeArrays(nums1, m, nums2, n, m + n - 1);
    }
    private void mergeArrays(int[] nums1, int m, int[] nums2, int n, int index) {         if (n == 0) {             return;         }         // 根据当前元素的大小关系,逐步将较大的元素放入 nums1 的末尾,直到合并完成。         if (m == 0 || nums1[m - 1] <= nums2[n - 1]) {             nums1[index] = nums2[n - 1];             mergeArrays(nums1, m, nums2, n - 1, index - 1);         } else {             nums1[index] = nums1[m - 1];             mergeArrays(nums1, m - 1, nums2, n, index - 1);         }     }
}

标签:递归,int,元素,合并,力扣,88,数组,nums1,nums2
From: https://www.cnblogs.com/JavaYuYin/p/18012221

相关文章

  • 力扣递归之21. 合并两个有序链表
    将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=[0]输出:[0]classSolution{publicListN......
  • python turtle 递归绘制树
    运行效果代码importturtleastimportrandomasrc=["pink","green","lightgreen","orange","red","purple"]defdrawStar(l):t.begin_fill()foriinrange(5):t.forward(l)......
  • RAPTOR:递归摘要与树形检索的结合,提升RAG检索性能
    RAPTOR:递归摘要与树形检索的结合,提升RAG检索性能来源:ICLR'24https://arxiv.org/pdf/2401.18059.pdf随着LLM技术的发展,RAG的价值也来越明显,可以视作LLM应用、落地的一个主要方向。RAG通过结合检索系统和生成模型,在生成回答时先从外部知识库种检索相关信息,辅助LLM进行更......
  • 「杂题乱刷」CF1886D
    题目链接简单计数题。容易看出\(<,>\)这两个符号一定只有\(1\)种选择,而\(?\)就有\(i-1\)中选择,总方案数很好推出,这样时间复杂度为\(O(nm)\),不能通过此题,因此我们考虑用逆元优化,优化后时间复杂度\(O(m)\)。参考代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?......
  • (14/60)二叉树理论基础、递归遍历、迭代遍历、统一迭代
    二叉树理论基础分类满二叉树:只有度为0和度为2的结点,且度为0结点在同一层上(每一层的结点都是满的)。完全二叉树:除了底层外其他层结点都是满的(底层当然也可以是满的),且底层结点从左往右连续不断。二叉搜索树:树的每个结点满足:左子树所有结点值均小于根结点的值右子树所有......
  • 代码随想录算法训练营第十四天| 理论基础 递归遍历 迭代遍历 统一迭代
    理论基础代码随想录(programmercarl.com)二叉树的链接形式定义(防忘)structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(NULL),right(NULL){}};额外补充(关于unordered_map和map)unordered_map和map类似,都是存储......
  • 递归魔法
    反转单链表的迭代实现不是一个困难的事情,但是递归实现就有点难度了,如果再加一点难度,让你仅仅反转单链表中的一部分,你是否能够递归实现呢?本文就来由浅入深,stepbystep地解决这个问题。如果你还不会递归地反转单链表也没关系,本文会从递归反转整个单链表开始拓展,只要你明白单链表......
  • 力扣刷题——SQL
    力扣刷题——高频SQL50题:题目链接:https://leetcode.cn/problems/department-top-three-salaries/?envType=study-plan-v2&envId=sql-free-50185.部门工资前三高的所有员工:表:Employee:Department+--......
  • 递归
    递归A方法调用B方法,我们很容易理解!递归就是:A方法调用A方法!!就是自己调用自己!!利用递归可以用简单的程序来解决一些复杂的问题。它通常把一个大型复杂的问题层层转化为一个与原问题相似的的规模较小的问题来求解。递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复......
  • 洛谷题单指南-递推与递归-P1464 Function
    原题链接:https://www.luogu.com.cn/problem/P1464题意解读:虽然a、b、c可输入的范围比较大,但是递归中,只会限制在0-20以内,由于递归中有大量的重复计算,因此需要采用记忆化搜索来保存已经计算过的递归函数值。解题思路:定义三位数组LLmem[25][25][25],mem[a][b][c]保存w(a,b,c)的......