递归合并两个已按升序排列的数组

发表于 | 分类于

我这个人，一般现场做或者线上做面试题，表现都很差，但是給我一个IDE，我就起飞了，面向IDE编程的选手。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package com.alonelaval.java.leetcode;
import java.util.Arrays;
/**
 * @author huawei
 * @create 2019-11-28
 **/
public class Code2 {
    /**
     * 递归合并两个已按升序排列的数组.
     *
     * <p>
     *   提示：
     *     1. 必须使用递归写法，循环写法无效。
     *     2. 可以定义辅助函数。
     *     3. test case执行时可能出现StackOverFlowError。
     * </p>
     *
     * @param a 升序排列数组，长度可能为0-10000
     * @param b 升序排列数组，长度可能为0-10000
     * @return a和b合并后的升序排列数组
     */
    public static int[] merge(int[] a, int[] b) {
        if(a == null || b== null){
            return a==null ? b :a;
        }
        int [] result = new int[a.length+b.length];
        return merge(a,b,0,0,result,0);
    }
    public static int[] merge(int []a,int [] b,int aIndex,int bIndex,int []result,int resultIndex){
        if(result.length ==resultIndex){
            return result;
        }
        if(aIndex == a.length){
            result[resultIndex++]=b[bIndex++];
            return merge(a,b,aIndex,bIndex,result,resultIndex);
        }
        if(bIndex == b.length){
            result[resultIndex++]=a[aIndex++];
            return merge(a,b,aIndex,bIndex,result,resultIndex);
        }
        if(a[aIndex] == b[bIndex]){
            result[resultIndex++] = a[aIndex++];
            result[resultIndex++] = b[bIndex++];
        }
        else if (a[aIndex] < b[bIndex]) {
            result[resultIndex++] = a[aIndex++];
        }
        else if (a[aIndex] > b[bIndex]) {
            result[resultIndex++] = b[bIndex++];
        }
        return merge(a,b,aIndex,bIndex,result,resultIndex);
    }
    public static void main(String[] args) {
        int a []= new int[]{1,3,5,12,12,12,12};
        int b []= new int[]{2,4,62,90};
        System.out.println(Arrays.toString(merge(a,b)));
    }
}