当前位置: 首页 > article >正文

【LeetCode 88. 合并两个有序数组】 java实现

LeetCode 88. 合并两个有序数组

题目描述

给你两个有序整数数组 nums1nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

说明:

  • 初始化 nums1nums2 的元素数量分别为 mn
  • 你可以假设 nums1 的大小等于 m + n(即它有足够的空间存放 nums2 中的元素)。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]

Java 实现解法

方法一:双指针从后向前合并
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1; // nums1的当前索引
        int p2 = n - 1; // nums2的当前索引
        int p = m + n - 1; // nums1的末尾索引

        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p--] = nums1[p1--];
            } else {
                nums1[p--] = nums2[p2--];
            }
        }

        // 如果nums2还有剩余,直接拷贝到nums1前面
        while (p2 >= 0) {
            nums1[p--] = nums2[p2--];
        }
    }
}

解题思路

  • 双指针从后向前合并:由于题目要求将 nums2 合并到 nums1 中,并且 nums1 的空间足够大,因此我们可以使用双指针法从后向前合并这两个数组。这样做的好处是可以避免在合并过程中对 nums1 的覆盖,从而丢失尚未处理的数据。
  • 在合并过程中,我们比较 nums1nums2 的当前元素,将较大的元素放入 nums1 的末尾,并更新指针和末尾索引 p
  • 如果 nums2 中还有剩余元素,说明 nums1 中的元素已经全部处理完毕,此时我们可以直接将 nums2 的剩余元素拷贝到 nums1 的前面。

这种方法的时间复杂度是 O(m+n),其中 mn 分别是 nums1nums2 的长度,因为每个元素我们至多处理一次。空间复杂度是 O(1),因为我们是在原地修改 nums1

注:来源leetcode网站


http://www.kler.cn/a/355381.html

相关文章:

  • Java 中压缩图片并应用 EXIF 旋转信息
  • Linux 常见用例汇总
  • 算法,递归和迭代
  • 03.01、三合一
  • 专业的内外网数据交换方案 可解决安全、效率、便捷3大问题
  • Java爬虫获取1688 item_search_img接口详细解析
  • 无人机集群路径规划:5种优化算法(SFOA、APO、GOOSE、CO、PIO)求解无人机集群路径规划,提供MATLAB代码
  • 操作系统学习笔记-1.1操作系统的基本概念
  • 抖音大模型面试经历分享
  • docker搭建 Rancher开源的 Kubernetes管理平台
  • C语言中的文件操作:从基础到深入底层原理
  • Blob 学习指南:从零开始学习 JavaScript Blob 对象的使用
  • Ubuntu 安装 nginx
  • 【RS】GEE(Python):基础知识与环境搭建
  • 第二十三篇——解析几何:用代数的方法解决更难的几何题
  • C++AVL树的介绍和实现
  • ROS2 通信三大件之动作 -- Action
  • Oracle漏洞修复 19.3 补丁包 升级为19.22
  • React路由 基本使用 嵌套路由 动态路由 获取路由参数 异步路由 根据配置文件来生成路由
  • 反向传播算法(Backpropagation)
  • Vulnhub打靶-admx-new
  • JavaWeb合集08-项目开发实战
  • 1022. 宠物小精灵之收服
  • mysql数据同步ES方案---Canal
  • Mybatis中的映射文件编写原则
  • ssh远程打开图形化程序