目前看到题目的解法,大多为 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;
    }
}

如有问题请指正,感谢。

待润色。



版权声明:本文为O_Victorain原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/O_Victorain/article/details/82564375