本文共 3396 字，大约阅读时间需要 11 分钟。

问题

合并两个已排序的数组

输入：arr1 [] = {
   1，3，4，5}，arr2 [] = {
   2，4，6，8}输出：arr3 [] = {
   1,2,3,4,4,5,6 8}

解决

思路

1.两个数组A,B,创建第三个数组C,C的长度为AB之和

先将A的值逐个赋给C

两次遍历

遍历B取出B的元素 遍历C中的元素,遍历次数等于A.length+Bi,因为随着B元素的插入,C的元素在不断增长 可以设想: Bi元素假如找到C中一个合适的位置想要插入,就需要此元素后的所有元素向后移动一个位置 即此时所有应该向后移动的元素可以看做一个后缀整体,只需保留C中待插入位置之前的元素顺序,然后将后缀重新再赋予即可 此时Bi向C插入元素有三种可能性 在C之前插入,之间插入,之后插入 "之间"插入的只需要比较两边的值,不小于前一个,小于后一个 "之前"插入的只小于第一个(因为事先已经排序,不会有再比AB最小值再小的元素) "之后"插入的必定大于当前C数组最后一个元素

优化:因为都是升序排序,B向A中插入元素后可以保留此元素坐标,下次B元素直接在上次B元素插入的坐标位置后比较即可,坐标之前的不用比较,因为坐标之前的元素没有比当前B元素再大的了

package array;import java.util.ArrayList;import java.util.Arrays;/** * @ClassName MegerArray * Description TODO **/public class MegerArray {
       public static void main(String[] args) {
           int[] arr1 = {
    1, 3, 4, 5,6}, arr2 = {
   -1,0,0,1,2,3,7,8,9,10,10,10,90,98,98,98},arr3=new int[100];        MegerArray megerArray = new MegerArray();        megerArray.megerArray(arr1,arr2,arr3);    }    /*另外一种思路是使用一个数组吸收所有数据然后排序即可*/    /*此种算法也许最难*/    /*我希望这里A最长,则比较的次数相对较小*/    public void  megerArray(int[] A,int[] B,int[] C) {
           for (int i = 0; i < A.length; i++) {
               C[i] = A[i];        }        int allLong=A.length + B.length;        int index = 0;        int count=0;        for (int i = 0; i < B.length; i++) {
               System.out.println("数据检测" + B[i]);            for (int i1 = index; i1 
   
    =C[A.length+i-1]) {
                       C[A.length+i] = B[i];                    System.out.println(Arrays.toString(C));                    index=A.length+i-1;                    break;                }                /*中间插入*/                if (B[i] >= C[i1] && B[i] < C[i1+1]) {
                       index=i1;                    System.out.println("条件符合");                    int[] saveSuffix=new int[A.length+i-i1-1];                    for (int i2 = i1+1,temp=0; i2 
   

2.将两个数组的最小值比较,每次将最小的插入C中

然后将还有剩余的数组直接加在末尾即可

此种方法简单

package array;import java.util.Arrays;/** * @ClassName MergeSimple * Description TODO **/public class MergeSimple {
       public static void main(String[] args) {
           int[] arr1 = {
   1, 3, 4, 5, 6}, arr2 = {
   -1, 0, 0, 1, 2, 3, 7}, arr3 = new int[100];        int i = 0,j=0,k=0;        while(i

可能会有疑问,假如1 3 5, 2 4 6,最后只比较最小值得到的不是1 2 3 4 5吗?

比较到5就会退出循环,因为此时i已经到3,等于了A的长度 所以才有后面的两个while,专门用于收集那些未比较的数据

3.还有一种方法,使用hashmap

hashmap的特性

package array;// Java program to merge two sorted arrays//using mapsimport java.io.*;import java.util.*;class TestHash {
       // Function to merge arrays    static void mergeArrays(int a[], int b[], int n, int m) {
   // Declaring a map.// using map as a inbuilt tool// to store elements in sorted order.        Map
   
     mp = new HashMap
    
     ();// Inserting values to a map.        for (int i = 0; i < n; i++) {
               mp.put(a[i], true);        }        for (int i = 0; i < m; i++) {
               mp.put(b[i], true);        }// Printing keys of the map.        for (Map.Entry
     
       me : mp.entrySet()) {
               System.out.print(me.getKey() + " ");        }    }    // Driver Code    public static void main(String[] args) {
           int a[] = {
   1, 3, 5, 7}, b[] = {
   2, 4,4, 6, 8};        int size = a.length;        int size1 = b.length;// Function call        mergeArrays(a, b, size, size1);    }}// This code is contributed by rag2127
     
    
   

entryset比普通的key,然后value获取值更快,因为提前获得了key-value对象,后面只是从对象集合中查询