[Java] 找出两有序数组第 k 大的值_java 两个升序数组找出第k大的数字

目前看到题目的解法，大多为 C++ 实现 ，且有些代码不完善，故在此赘述。总的来说，主要有以下 3 种方式：

• a： 合并数组后排序
• b： 两指针遍历并计数
• c： 二分法

分析

假如两数组长度分别为 m 和 n (且让 m < n)，求第 k 大的数，以上 3 种方式中：
a 时间复杂度为视排序算法而定，因此处数组有序，故归并排序最为方便，但时间复杂度为 O((m+n)log(m+n))，另外需要辅助空间为 m + n 的数组；b 时间复杂度，为 O(m + n)（k 可能无限接近 m + n ）；c 的时间复杂度为 O((m+n)log(m+n))，并且无需辅助空间。
c 的具体方式有两种，一种是每次对数组(即 m 与 n)二分，一种是每次对 k 二分，此处我们采用第二种方式。以下为代码实现：

import java.util.Arrays;

/**
 * 找出两个有序数组第 k 大的数（假设从小到大排序），且此处认为 arrA.length < arrB.length
 * 
 * @author Victor
 *
 */
public class SortedArrayFindK {
    public static void main(String[] args) {
        int[] arrA = new int[] { 10, 11, 12, 13, 14 };
        int[] arrB = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int k = 6;

        System.out.println(findBigK(arrA, 0, arrA.length - 1, arrB, 0, arrB.length - 1, k));
        System.out.println(findBigKMS(arrA, arrB, k));
    }

    /**
     * 找出两个有序数组第 k 大的数（假设从小到大排序），且此处认为 arrA.length < arrB.length
     * 
     * @param arrA
     *            数组 A
     * @param la
     *            数组 A 范围左边界
     * @param ra
     *            数组 A 范围右边界
     * @param arrB
     *            数组 B
     * @param lb
     *            数组 B 范围左边界
     * @param rb
     *            数组 B 范围右边界
     * @param k
     *            第 k 大
     * @return 第 k 大的数
     */
    public static int findBigK(int[] arrA, int la, int ra, int[] arrB, int lb, int rb, int k) {
        // 排除数组长度为 0 及数组右越界的情况
        if (arrA.length == 0 || la > ra) {
            return arrB[lb + k - 1];
        }
        if (arrB.length == 0 || lb > rb) {
            return arrA[la + k - 1];
        }

        // k 为 1 时，亦为算法的边界情况，直接处理
        if (k == 1) {
            return min(arrA[la + k - 1], arrB[lb + k - 1]);
        }

        // 取两者较小值，以免 k / 2 较大时数组越界
        int ka = min(k / 2, ra - la + 1);
        int kb = min(k - ka, rb - lb + 1);

        if (arrA[la + ka - 1] > arrB[lb + kb - 1]) {
            return findBigK(arrA, la, la + ka - 1, arrB, lb + kb, rb, k - kb);
        } else {
            return findBigK(arrA, la + ka, ra, arrB, lb, lb + kb - 1, k - ka);
        }
    }

    /**
     * 数组合并后排序，然后找出第 k 大的值
     */
    public static int findBigKMS(int[] arrA, int[] arrB, int k) {
        int[] arrC = new int[arrA.length + arrB.length];

        System.arraycopy(arrA, 0, arrC, 0, arrA.length);
        System.arraycopy(arrB, 0, arrC, arrA.length, arrB.length);
        Arrays.sort(arrC);

        return arrC[k - 1];
    }

    /**
     * 取较小值
     */
    public static int min(int a, int b) {
        return a > b ? b : a;
    }
}
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

如有问题请指正，感谢。
待润色。