Java算法（递归）：两个不同长度的有序数组求第k小的元素（时间复杂度为：O(log(m1 + m2))）。

首先看到时间复杂度要求就可以确定使用折半查找的思想。由于数组下标是从0开始计数，我们可以将k也定义为从0开始，那么原本题目中的第k小（k从1开始），在我们算法中就表示成第k-1小（k从0开始）。

注意每次取mid1和mid2时，都应该考虑有没有越界情况的发生。

public class ex_2 {
    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 2, 3};
        int[] arr2 = new int[]{0, 4, 5, 6, 7, 8};
        System.out.println(findKth(arr1, arr2, 2));
    }

    public static int findKth(int[] arr1, int[] arr2, int k) {
        if (arr1 == null || arr1.length < 1) {
            return arr2[k - 1];
        }
        if (arr2 == null || arr2.length < 1) {
            return arr1[k - 1];
        }
        return findKth(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k - 1);
    }

    public static int findKth(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2, int k) {
        if (l1 > r1) {
            return arr2[l2 + k];
        }
        if (l2 > r2) {
            return arr1[l1 + k];
        }
        if (k == 0) {
            return Math.min(arr1[l1], arr2[l2]);
        }
        int mid1 = l1 + k / 2 < r1 ? l1 + k / 2 : r1;
        int mid2 = l2 + k / 2 < r2 ? l2 + k / 2 : r2;
        if (arr1[mid1] < arr2[mid2]) {
            return findKth(arr1, mid1 + 1, r1, arr2, l2, r2, k - (k / 2) - 1);
        } else if (arr1[mid1] > arr2[mid2]) {
            return findKth(arr1, l1, r1, arr2, mid2 + 1, r2, k - (k / 2) - 1);
        } else {
            return arr2[mid2];
        }
    }
}

 

本文地址：https://blog.csdn.net/qq_37089829/article/details/109270881