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 分别为短数组和长数组的长度
去除掉后面大的,直接求中位数
求 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]
求 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]
求 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
求 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)