欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer算法(二)

程序员文章站 2024-01-03 19:41:58
...

将两个有序的数组合并成一个有序的数组

在通常情况下,我们会开辟一个新的数组,然后比较两个数组的数字,然后将小的依次放入其中,这样做时间复杂度没有太大,但是空间复杂度大了


初始化arr1数组,长度大于arr1和arr2长度之和,然后从后向前依次比较,从arr2中找出一个大于arr1的数字,然后插入到这个数字后面,依次循环,直到两个指针都指向数组的头

剑指offer算法(二)

package com.tangbaobao.offer;

/**
 * 数组合并
 *
 * @author 唐学俊
 * @create 2018/03/29
 **/

import org.junit.Test;

import java.util.Arrays;

/**
 * 有两个已经排序的数组,A1,A2,内存在A1的末尾有足够的空间容纳A2,请实现一个函数,把A2中的所有数字插入到A1中
 * 并且所有的数字都是排序的
 */
public class Test4 {

    @Test
    public void fun1() {
        int[] arr1 = new int[20];
        arr1[0] = 1;
        arr1[1] = 3;
        arr1[2] = 5;
        arr1[3] = 7;
        arr1[4] = 9;
        arr1[5] = 11;
        int[] arr2 = {2, 4, 6, 8, 10};
        int[] ints = this.merryArray(arr1, arr2);
        System.out.println(Arrays.toString(ints));

    }

    public int[] merryArray(int[] arr1, int[] arr2) {
        //初始化实际长度
        /**
         * 注意:这里的长度不是arr1的长度,而是arr1中实际存有多少个数
         */
        int arr1Length = 5;

        //定义两个指针,一个指向arr1,一个指向arr2
        int point1 = arr1Length - 1;
        int point2 = arr2.length - 1;
        while (point1 >= 0 && point2 >= 0) {
            if (arr2[point2] >= arr1[point1]) {
                arr1Length++;
                //将arr2的数组插入到arr1的后面
                for (int i = arr1Length; i > point1; i--) {
                    arr1[i] = arr1[i - 1];
                }
                //将新的值插入在arr1数中比较的后一个
                arr1[point1 + 1] = arr2[point2];
                //arr2指针后移
                point2--;
            } else {
                //arr1指针后移
                point1--;
            }
        }
        return arr1;
    }
}
相关标签: 数组的合并

上一篇:

下一篇: