剑指offer算法(二)
程序员文章站
2024-01-03 19:41:58
...
将两个有序的数组合并成一个有序的数组
在通常情况下,我们会开辟一个新的数组,然后比较两个数组的数字,然后将小的依次放入其中,这样做时间复杂度没有太大,但是空间复杂度大了
初始化arr1数组,长度大于arr1和arr2长度之和,然后从后向前依次比较,从arr2中找出一个大于arr1的数字,然后插入到这个数字后面,依次循环,直到两个指针都指向数组的头
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;
}
}