Leetcode#88. Merge Sorted Array(合并两个有序数组)

题目描述

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
  • 你可以假设 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]

思路

思路一:

从两个数组中的末尾开始进行合并,先找两个数组中较大的移动到正确的位置,将那个移动的位置值向前移动一个位置,再进行同样的操作,直到所有的元素处理完。

代码实现

package Array;

/**
 * 88. Merge Sorted Array(合并两个有序数组)
 * 给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
 */
public class Solution88 {
    public static void main(String[] args) {
        Solution88 solution88 = new Solution88();

        solution88.merge();
    }

    /**
     * 从两个数组中的末尾开始进行合并,先找两个数组中较大的移动到正确的位置,将那个移动的位置值向前移动一个位置,再进行同样的操作,直到所有的元素处理完。
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[index--] = nums1[i--];
            } else {
                nums1[index--] = nums2[j--];
            }
        }
        while (j >= 0) {
            nums1[index--] = nums2[j--];
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏海天一树

图的深度优先搜索

图有两种最基本的搜索算法,一种是深度优先搜索,另一种是广度优先搜索。本节先介绍深度优先搜索。

972
来自专栏和蔼的张星的图像处理专栏

422. 最后一个单词的长度 从后向前遍历

给定一个字符串, 包含大小写字母、空格' ',请返回其最后一个单词的长度。 如果不存在最后一个单词,请返回 0 。 样例 给定 s = "Hello Wo...

932
来自专栏Python小屋

Python编程一定要注意的那些“坑”(四)

已发过的“坑”请参考Python函数默认值参数的2个坑,Python编程中一定要注意的那些“坑”(一),Python编程中一定要注意的那些“坑”(二),Pyth...

36813
来自专栏编程理解

排序算法(五):堆排序

的时间复杂度即可将二叉树重新调整为有序状态。若构造出一种具有特殊节点顺序的二叉树,使得每次对二叉树执行插入或删除节点操作后,都调整保持二叉树根节点的值为树中节...

1802
来自专栏mathor

波兰表达式

1874
来自专栏mathor

LeetCode164. 最大间距

 这道题用到了桶排序的思想,但是跟排序没啥关系,思路是这样的,数组中有n个元素,那么就构建n+1个桶,桶的属性有三个,最大值最小值以及是否为空。桶的下标从0...

1152
来自专栏从零开始的linux

python运算符

算数运算符 符号描述例子-减法3 - 2=1+加法3 + 2=5*乘法3 * 2=6/除法4 / 2=2%取模 取余数3 % 2=1**幂2 ** 3=8//取...

4338
来自专栏java学习

Java基础第五天学习笔记

05.01_Java语言基础(数组概述和定义格式说明)(了解) * A:为什么要有数组(容器) * 为了存储同种数据类型的多个值 * B:数组概念 * 数组...

2957
来自专栏运维技术迷

PHP-数组排序

分别定义一个数值数组和一个关联数组. $age=array("lili"=>"23","bob"=>"30","ben"=>"44"); $c...

3196
来自专栏编程理解

排序算法(十):基数排序

基数排序也可以称为多关键字排序,同计数排序类似,也是一种非比较性质的排序算法。将待排序集合中的每个元素拆分为多个总容量空间较小的对象,对每个对象执行桶排序后,则...

7041

扫码关注云+社区

领取腾讯云代金券