题解 | #在两个排序数组中找到第k小的数#

import java.util.Scanner;

public class Main{
    public static int getUpMedian2(int[] arr1, int s1, int e1, int[] arr2, int s2, int e2) {
        if (arr1 == null || arr2 == null) {
            return -1;
        }

        int mid1 = 0;
        int mid2 = 0;
        int offset = 0;
        while (s1 < e1) {
            mid1 = (s1 + e1) / 2;
            mid2 = (s2 + e2) / 2;
            offset = ((e1 - s1 + 1) & 1) ^ 1;
            if (arr1[mid1] > arr2[mid2]) {
                e1 = mid1;
                s2 = mid2 + offset;
            } else if (arr1[mid1] < arr2[mid2]) {
                s1 = mid1 + offset;
                e2 = mid2;
            } else {
                return arr1[mid1];// 返回 arr2[mid2]也可以
            }
        }
        return Math.min(arr1[s1], arr2[s2]);
    }

    public static int findKthNum(int[] arr1, int[] arr2, int Kth) {
        if (arr1 == null || arr2 == null) {
            throw new RuntimeException("Your arr is invalid");
        }
        if (Kth < 1 || Kth > arr1.length + arr2.length) {
            throw new RuntimeException("K is invalid");
        }
        int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
        int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
        int l = longs.length;
        int s = shorts.length;
        if (Kth <= s) {
            return getUpMedian2(shorts, 0, Kth - 1, longs, 0, Kth - 1);
        }
        if (Kth > l) {
            if (shorts[Kth - l - 1] >= longs[l - 1]) {
                return shorts[Kth - l - 1];
            }
            if (longs[Kth - s - 1] >= shorts[s - 1]) {
                return longs[Kth - s - 1];
            }
            return getUpMedian2(shorts,Kth-l,s-1,longs,Kth-s,l-1);
        }
        if (longs[Kth - s - 1] >= shorts[s - 1]) {
            return longs[Kth - s - 1];
        }
        return getUpMedian2(shorts,0,s-1,longs,Kth-s,Kth-1);

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] str=in.nextLine().split(" ");
        int n=Integer.parseInt(str[0]);
        int m=Integer.parseInt(str[1]);
        int k=Integer.parseInt(str[2]);
        int[] arr1=new int[n];
        int[] arr2=new int[m];
        for (int i = 0; i < n; i++) {
            arr1[i]=in.nextInt();
        }
        for (int i = 0; i <m ; i++) {
            arr2[i]=in.nextInt();
        }
        int res=findKthNum(arr1,arr2,k);
        System.out.println(res);

    }
}