082 在两个排序数组中找到第k小的数
Table of Contents

ac

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int[] a1 = new int[n];
        int[] a2 = new int[n];
        for(int i=0;i<n;i++){
            a1[i] = sc.nextInt();
        }
        for(int i=0;i<m;i++){
            a2[i] = sc.nextInt();
        }
        int minK = -1;
        if(n < m) {
            minK = getMinK(0, n - 1, a1, 0, m - 1, a2, k);
        }else{
            minK = getMinK(0, m - 1, a2, 0, n - 1, a1, k);
        }
        System.out.println(minK);
    }

    // 两个排序数组,求k小
    static int getMinK(int left1, int right1, int[] sArr,
                       int left2, int right2, int[] lArr, int k){
        int s = right1 - left1 + 1;
        int l = right2 - left2 + 1;
        if(k <= 0 || k > (s + l)){
            return -1;
        }
        // 特殊情况1
        if(sArr[right1] <= lArr[left2]){
            if(k <= s){
                return sArr[k-1];
            }else {
                return lArr[k - s - 1];
            }
        }
        // 特殊情况2
        if(lArr[right2] <= sArr[left1]){
            if(k <= l){
                return lArr[k-1];
            }else {
                return sArr[k - l - 1];
            }
        }

        if(k <= s){
            // 两个数组的长度都是k, 上中位数就是第k小的那个数
            return getUpMedian(0, k-1, sArr, 0, k-1, lArr);
        }

        if(k > l){
            // lArr 最大的 小于 sArr[k - l - 1]
            if(sArr[k - l - 1] >= lArr[l-1]){
                return sArr[k-l-1];
            }
            // sArr 最大的 小于 lArr[k-s-1]
            if(sArr[s-1] <= lArr[k-s-1]){
                return lArr[k-s-1];
            }
            return getUpMedian(k-l, s-1, sArr, k-s, l-1, lArr);
        }

        // k > s && k <= l
        // sArr 最大的 小于 lArr[k-s-1]
        if(sArr[s-1] < lArr[k-s-1]){
            return lArr[k-s-1];
        }

        return getUpMedian(0, s-1, sArr, k-s, k-s-1 + s, lArr);
    }

    // 是否奇数
    static boolean isOdd(int val){
        if(val % 2 == 1){
            return true;
        }
        return false;
    }

    // 两个一样长度的排序数组的上中位数
    // 偶数取中间两个的前一个(例:总共有8个数,上中位数是第4小的数)
    static int getUpMedian(int left1, int right1, int[] a1,
                           int left2, int right2, int[] a2){
        if(left1 == right1){
            return Math.min(a1[left1], a2[left2]);
        }
        if(a1[right1] < a2[left2]){
            return a1[right1];
        }else if(a2[right2] < a1[left1]){
            return a2[right2];
        }else {
            while (left1 < right1) {
                int mid1 = (right1 + left1) / 2;
                int mid2 = (right2 + left2) / 2;
                if (a1[mid1] < a2[mid2]) {
                    if (isOdd(right1 - left1 + 1)) {
                        // 包括mid在内
                        left1 = mid1;
                        right2 = mid2;
                    }else {
                        left1 = mid1 + 1;
                        right2 = mid2;
                    }
                }else if (a1[mid1] > a2[mid2]) {
                    if (isOdd(right1 - left1 + 1)) {
                        // 包括mid在内
                        left2 = mid2;
                        right1 = mid1;
                    }else {
                        left2 = mid2 + 1;
                        right1 = mid1;
                    }
                }else {
                    return a1[mid1];
                }
            }
            return Math.min(a1[left1], a2[left2]);
        }
    }

}
/*
5 3 1
1 2 3 4 5
3 4 5

1

3 4 4
1 2 3
3 4 5 6

3
 */

s,l 分别为短数组和长数组的长度

k <= s 的情况

去除掉后面大的,直接求中位数

k > l 的几种情况

情况1(特殊情况1)

 12th  k = 12

1 8 [28] 29 30 (s=5)

1 2 9 10 12 18 20 22 26 (l=9)

28 > 26 那么就是28了,即:sArr[k - l - 1] >= lArr[l-1]

情况2(特殊情况2)

 12th  k = 12

1 8 28 29 30 (s=5)

1 2 9 10 12 18 [31] 32 33 (l=9)

31 > 30 那么就是31了,即: sArr[s-1] <= lArr[k-s-1]

情况3(一般情况)

 12th  k = 12

1 8 28 29 30 (s=5)

1 2 9 10 12 18 29 32 33 (l=9)

sArr去掉了k - l(因为显然不会是)
lArr去掉了k - s(因为显然不会是)

再求 s - (k-l)   l - (k-s) 的上中位数即可,即:(k-l, s-1, sArr, k-s, l-1, lArr)

证明:
(k-l) + (k-s) + [(s - (k-l)) + l - (k-s)] / 2 = k

k > s && k <= l

 7th k=7

1 8 28 29 30 (s=5)

1 [2] 9 10 12 18 29 32 33 (l=9)

lArr的前两个肯定不是了

1 8 28 29 30
9 10 12 18 29

其中如果:sArr[s-1] < lArr[k-s-1],那么就是lArr[k-s-1]

否则lArr的前面部分是可以排除的,即(0, s-1, sArr, k-s, k-s-1 + s, lArr)