[牛客算法系列] 在两个排序数组中找到第k小的数

题目

• 给定两个有序数组arr1,arr2, 再给定一个整数k, 返回所有数中第k 小的数。
• 比如 arr1 = [1,2,3,4,5], arr2 = [3,4,5], k =1.
  1 是所有数中第一小的数，所以返回1.
  arr1 = [1,2,3], arr2 = [3,4,5,6] , k = 4.
  3 是所有数中第4 小的数，所以返回3.
• Note： 如果arr1 的长度为N， arr2 的长度为M， 时间复杂度要达到O(log(min{M,N})),额外空间复杂度O(1).

分析题目

• 本题深度的利用“在两个长度相等的排序数组中找到上中位数”
• 分四种情况 详见代码

代码

//两个长度相等的排序数组中找到上中位数
public int getUpMedian(int[] a1, int s1, int e1, int[] a2, int s2, int e2) {
	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;  //偶数offset 为1， 奇数为0
		if(a1[mid1] > a2[mid2]){
			e1 = mid1;
			s2 = mid2 + offset;
		}else if(a1[mid1] < a2[mid2]){
			s1 = mid1 + offset;
			e2 = mid2;
		}else{
			return a1[mid1];
		}
	}
	return Math.min(a1[s1],a2[s2]);
}

public int findKthNum(int[] arr1, int[] arr2, int kth){
	if(arr1 == null || arr2 == null){
		throw new RuntimeException("Your arr is invalid!");
	}
	// ① kth < 1 或大于 两个数组长度的和，则k 无效 
	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;
	//② kth 小于较小数组的长度(从arr1，arr2 中分别拿k 个 求上中位数)
	if(kth <= s){
		return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1)
	}
	//③ kth 大于较长数组的长度。先判断两个数组在kth 位置的大小
	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 getUpMedian(shorts, kth -l , s -1, longs, kth -s , l - 1);		
	
	}
	//④ kth 在两者之间。先判断长数组中kth 位置的大小
	if(longs[kth -s -1] >= shorts[s -1]){
		return longs[kth -s -1];
	}
	return getUpMedian(shorts, 0, s-1, longs, kth -s,, kth - 1)
}