Java刷题篇——合并两个有序数组

2023-12-14 21:51:11

1.题目描述

给出一个有序的整数数组A 和有序的整数数组 B,请将数组B合并到数组A中,变成一个有序的升序数组。

数据范围:0 <= n,m <= 100, |A~i~| <= 100, |B~i~| <= 100

注意:

  1. 保证 A 数组有足够的空间存放 B 数组的元素, A 和 B 中初始的元素数目分别为 m 和 n,A的数组空间大小为 m+n
  2. 不要返回合并的数组,将数组 B 的数据合并到 A 里面就好了,且后台会自动将合并后的数组 A 的内容打印出来,所以也不需要自己打印
  3. A 数组在[0,m-1]的范围也是有序的

示例1

输入:[4,5,6],[1,2,3]

返回值:[1,2,3,4,5,6]

说明:A数组为[4,5,6],B数组为[1,2,3],后台程序会预先将A扩容为[4,5,6,0,0,0],B还是为[1,2,3],m=3,n=3,传入到函数merge里面,然后请同学完成merge函数,将B的数据合并A里面,最后后台程序输出A数组

示例2

输入:[1,2,3],[2,5,6]

返回值:[1,2,2,3,5,6]

2. 思路分析

  1. 题目已经明确表明,A数组足够大,那么我们就不需要开辟额外的空间,直接拿A 数组操作
  2. 因为是合并数组,所以就需要双指针,那么我们开辟指针i,指针j,一个指向A的m-1,一个指向B的n-1,两个指针移动前我们还需要定义一个index = m + n - 1代表合并数组的最后一个元素位置
  3. 开始移动,让A[i],B[j]比较谁大,谁大就合并谁
  4. 最后判断一下B合并完成没有,B没有合并完的话,直接把B丢进A

image-20231214205001863

3. 代码

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[index] = A[i];
                index--;
                i--;
            } else {
                A[index] = B[j];
                index--;
                j--;
            }
        }
        while (i >= 0) {
            A[index] = A[i];
            index--;
            i--;
        }
        while (j >= 0) {
            A[index] = B[j];
            index--;
            j--;
        }
    }
}

运行结果:

image-20231214203938660

4.复杂度分析

  • 时间复杂度:O(m + n)
  • 空间复杂度:O(1)

文章来源:https://blog.csdn.net/2301_79076048/article/details/135004119
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。