亲宝软件园·资讯

展开

面试常见算法题:两个有序数组合并和两个无序数组合并

Abel-彭 人气:0

  数组合并在找工作中笔试和面试都是常遇到的问题,实际上这个主要可以分为两大类进行解决。第一类就是这两个数组都是有序的数组,第二类是这两个数组都是无需数组。

第一类问题解决的时候稍微有些复杂,而第二类问题就比较简单。如果是两个无序数组进行合并,我们可以在次创建一个数组。并且这个新数组的长度是两个无序数组长度之

和。然后对这个新的数组进行一次排序就可以了,本篇文章主要使用冒泡排序。而对于两个有序数组合并的问题来说,我们就要考虑几种情况。第一种情况就是如果其中某一个数组的第一个元素比另外一个数组的最后一个元素大,那么就可以直接直接放到后面。第二种情况,就是两个数组进行一个一个比较,但如果其中有一个数组的元素已经遍历完了,而另外一个没有。

一.两个无序数组合并问题

/**
 * 合并两个无序的数组
 */
public class Test2 {
    public static void main(String[] args) {
        int[] array1={2,1,90,7,4,9};
        int[] array2={3,12,45,23,56};
        merge(array1,array2);
    }
    public static void merge(int[] array1,int[] array2){
        //定义一个变量
        int j=0;
        //定义一个新的数组
        int[] result=new int[array1.length+array2.length];
        for (int i = 0; i < array1.length; i++) {
            result[j++]=array1[i];
        }
        for (int n = 0; n < array2.length; n++) {
            result[j++]=array2[n];
        }
        //使用冒泡排序
        for (int i = 0; i < result.length-1; i++) {
            for (int n = 0; n < result.length-1-i; n++) {
                int temp=0;
                if(result[n]>result[n+1]){
                    temp=result[n+1];
                    result[n+1]=result[n];
                    result[n]=temp;
                }
            }
        }
        //进行遍历输出
        for (int i = 0; i < result.length; i++) {
            if(i==result.length-1){
                   System.out.print(result[i]+"]");
            }else if (i==0){
                System.out.print("["+result[i]+",");
            }else {
                System.out.print(result[i]+",");
            }
        }
    }
}

二.两个有序数组合并问题

import java.util.ArrayList;

/**
 * 将两个数组有序数组合并为一个有序数组
 */
public class Test {
    public static void main(String[] args) {
        //int[] array1={1,2,3,4};
        //int[] array1={1,3,5,7,9,13}int[] array2={5,6,7,8,9};;
        int[] array1={1,3,5,7,9,13};
        int[] array2={2,4,6,8,10,12};
        merge(array1,array2);
    }

    /**
     *
     * @param array1
     * @param array2
     */
    public static void merge(int[] array1,int[] array2){
        //定义两个变量
        int i=0;
        int j=0;
        int k=0;
        //在创建一个数组
        int[] result=new int[array1.length+array2.length];
        //如果数组arry1的第一个元素比array2最后一个元素大,那就直接把arry1数组元素放到array2后面
        if(array1[0]>array2[array2.length-1]){
            for (int m = 0; m < array2.length; m++) {
                result[k++]=array2[m];
            }
            for (int m = 0; m < array1.length; m++) {
                result[k++]=array1[m];
            }
        }
        //如果array2的第一个元素比array1的最后一个元素大,那么直接把array2的元素放到array1的后面
      else if (array2[0]>array1[array1.length-1]){
            for (int m = 0; m < array1.length; m++) {
                result[k++]=array1[m];
            }
            for (int m = 0; m < array2.length; m++) {
                result[k++]=array2[m];
            }
        }
      else {
            while (i < array1.length && j < array2.length) {
                if (array1[i] < array2[j]) {
                    //如果小就放到集合中
                    result[k++] = array1[i];
                    i++;
                } else {
                    result[k++] = array2[j];
                    j++;
                }
            }
            //如果array1都比较完了,剩下array2的就直接放到结果集中
            while (i == array1.length && j < array2.length) {
                result[k++] = array2[j++];
            }
            //如果array2都比较完了,剩下的array1就直接放到结果集中
            while (j == array2.length && i < array1.length) {
                result[k++] = array1[i++];
            }
        }
            //遍历输出所有的结果集
        bianli(result);
    }

    static void bianli(int[] result) {
        for (int s = 0; s< result.length; s++) {
            if(s==result.length-1){
                System.out.print(result[s]+"]");
            }else if (s==0){
                System.out.print("["+result[s]+",");
            }else {
                System.out.print(result[s]+",");
            }
        }
    }

}

 

加载全部内容

相关教程
猜你喜欢
用户评论