题目解析

给出两个排好序的数组，找出合并后的中位数。很基础，组合排序的中间流程，我面试候选者有时会考察这个题目

分析和思路方法

1、中位数为奇偶两类场景
2、输入两数组已排好序， 找到合并后（m+n）/2 或者 （m+n+1）/2 位置的数。 但是不需要使用合并新空间
3、两个数组同时遍历 查找其M=（m+n）/2 或者 （m+n+1）/2位置的数

代码演示：

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
/**
 * 很基础，组合排序的中间流程，我面试候选者有时会考察这个题目
 * 注意代码段和方法拆分， 这样可读性更强
 */
public class A4MedianOfTwoSortedArray {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int la = nums1.length;
        int lb = nums2.length;
        if (la == lb && lb == 0) {
            return 0;
        }
        if ((la + lb) % 2 == 0) {
            int m1 = (la + lb) / 2;
            int m2 = m1 + 1;
            return (findM(nums1, nums2, m1) + findM(nums1, nums2, m2)) * 1.0 / 2.0;
        } else {
            return findM(nums1, nums2, (la + lb + 1) / 2);
        }
    }

    /**
     * size(a) >size(b)
     *
     * @param a
     * @param b
     * @param m m<=size(a+b)
     * @return
     */
    private static int findM(int[] a, int[] b, int m) {
        int la = a.length;
        int lb = b.length;
        int counter = 0;
        int t1 = 0, t2 = 0;
        int result;
        while (true) {
            if (t1 == la) {
                result = b[t2];
                t2++;
            } else if (t2 == lb) {
                result = a[t1];
                t1++;
            } else if (a[t1] <= b[t2]) {
                result = a[t1];
                t1++;
            } else {
                result = b[t2];
                t2++;
            }
            counter++;
            if (counter == m) break;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1, 3, 5, 6}, new int[]{2, 7, 9, 10}));
    }

代码文件：
A4MedianOfTwoSortedArray.java

总结

  • 无他，良好习惯，代码片段方法抽离

版权声明：本文为博主原创文章，未经允许不得转载。