【Java 算法实现】合并两个有序数组(逆向双指针)

embedded/2024/9/23 10:23:49/

【Java 算法实现】合并两个有序数组

题目描述

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

你需要将 nums2 合并到 nums1 中,使合并后的数组同样保持非递减顺序排列。

注意:合并后的数组不应由函数返回,而是直接存储在 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素代表应合并的元素,后 n 个元素设为 0 以示占位,实际上应忽略。

示例

示例 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.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -10^9 <= nums1[i], nums2[j] <= 10^9

解决方案

逆向双指针

nums1的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者之中的较大者放进num1的最后面。

时间复杂度:O(m+n)。
指针移动单调递减,最多移动 m+n 次,因此时间复杂度为 O(m+n)。
空间复杂度:O(1)
直接对数组num1原地修改,不需要额外空间。

public class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m - 1, p2 = n - 1;int tail = m + n - 1;int cur;while (p1 >= 0 || p2 >= 0) {if (p1 == -1) {cur = nums2[p2--];} else if (p2 == -1) {cur = nums1[p1--];} else if (nums1[p1] > nums2[p2]) {cur = nums1[p1--];} else {cur = nums2[p2--];}nums1[tail--] = cur;}}public static void main(String[] args) {Solution solution = new Solution();int[] nums1 = {1, 2, 3, 0, 0, 0};int[] nums2 = {2, 5, 6};int m = 3, n = 3;solution.merge(nums1, m, nums2, n);System.out.println("Merged array:");for (int num : nums1) {System.out.print(num + " ");}}
}

http://www.ppmy.cn/embedded/32077.html

相关文章

python笔记:dataclass

1 引子&#xff1a;其他类似实现方法的局限性 假设我们现在需要实现这样的内容&#xff1a; nameChinaarea960population140967 1.1 tuple/list country1_tuple(China,960,140967) country1_tuple[0] #China 缺点&#xff1a;需要记住各个属性是list/tuple第几位的属性&am…

什么是CI/CD流水线

在软件开发中&#xff0c;流水线系统&#xff08;通常被称为CI/CD流水线或部署流水线&#xff09;是一种自动化的过程&#xff0c;用以快速、可靠地将软件从开发阶段引向生产阶段。CI代表持续集成&#xff08;Continuous Integration&#xff09;&#xff0c;而CD代表持续交付&…

行为型设计模式

一、责任链设计模式 &#xff08;一&#xff09;概念 使多个对象都有机会处理同一个请求&#xff0c;从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链&#xff0c;并沿着这条链传递该请求&#xff0c;直到有一个对象处理它为止。 &#xff08;二&#xf…

# 从浅入深 学习 SpringCloud 微服务架构(八)Sentinel(1)

从浅入深 学习 SpringCloud 微服务架构&#xff08;八&#xff09;Sentinel&#xff08;1&#xff09; 一、sentinel&#xff1a;概述 1、前言 – 服务熔断 Hystrix 的替换方案。 1&#xff09;2018年底 Netflix 官方宣布 Hystrix 已经足够稳定&#xff0c;不再积极开发 Hys…

快速入门Pandas和NumPy数据分析

大家好&#xff0c;从商业智能到科学研究&#xff0c;数据分析在许多领域中都是一项重要技能。Python因其可读性强和强大的库生态系统而成为最受欢迎的数据分析语言之一&#xff0c;Pandas和NumPy是重要的基础工具&#xff0c;适用于任何想要分析和解释数据的人。本文将探讨如何…

恶补《操作系统》4_1——王道学习笔记

4文件管理 4.1_1 初识文件管理 操作系统提供的功能&#xff1a; 处理机管理存储器管理文件管理设备管理 目标&#xff1a;安全高效 关于文件管理&#xff1a; 1&#xff09;计算机中存放了各种各样的文件&#xff0c;一个文件有哪些属性? 文件名:由创建文件的用户决定文件…

分片上传,分片合并

面是一种基于前端分片上传&#xff0c;后端合并的方法的代码实现&#xff1a; 前端代码&#xff08;HTML JavaScript&#xff09;&#xff1a; <input type"file" id"fileInput"> <button onclick"uploadFile()">Upload</butt…

深度学习之基于Matlab卷积神经网络验证码识别系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 一、项目背景 随着互联网的发展&#xff0c;验证码作为一种常用的安全验证手段&#xff0c;被广泛应用于各种网站和…