求两个有序数组的第k大的数

wuchangjian2021-11-04 12:04:36编程学习

题目:给定两个一维int数组A和B. 其中:A是长度为m、元素从小到大排好序的有序数组。B是长度为n、元素从小到大排好序的有序数组。希望从A和B数组中,找出最大的k个数字,要求:使用尽量少的比较次数。

解法:

1.首先介绍上中位数的概念(算法原型)

在编写判断上中位数的函数时,首先要保证两个数组的长度相同。

1.1 当两个数组长度均为偶数时

        eg:arr1 = {a,b,c,d};   arr2 = {e,f,g,h},求第4大的数

  1. 当 b==f 时,有 b,f均为上中位数      
  2. 当 b < f 时, abe 均小于 f,所以前三个最小的数中包含 ab;而 gh 大于 f,即 gh 大于abef,所以 gh 肯定不为第四大的数,所以第四大的数只能在 cd 和 ef 中产生,所以递归查找 cdef 中上中位数。
  3. 当 b > f 时, 同理可得第四大的数只能在 ab 和 gh 中产生,所以递归查找 abgh 上中位数。

1.2 当两个数组长度均为奇数时

        eg:arr1 = {a,b,c,d,e};   arr2 = {f,g,h,i,j},求第5大的数

  1. 当 c==h 时,有c,h均为上中位数
  2. 当 c < h 时,abc均小于h,fg 小于 h,所以 hij 肯定为第五位之后的数,那么只需考虑 abc 和 fg 是否符合要求。但是此时无法进行递归求解,因为两个数组长度不相等,所以要手动判断 c和g 的关系
    1. c==g:c,g均为上中位数
    2. c < g:abc 为前四小的其中三个数,所以第五大的数只能在 de 和 fg 中产生,所以递归查找 defg 中上中位数。
    3. c > g:abfg 均小于 c,c为上中位数
  3. 当 c > h 时:解法同2

2.题解

该题对于求解的第 k 大的数中的 k 参数有不同的求解方式,假设数组A长度为10,数组B长度为15

eg:注意:数组中的数字只代表位置,不表示值

arr1 = {1,2,3,4,5,6,7,8,9,10}     arr1.length = len1

arr2 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}     arr2.length = len2

2.1 当1<=k<=10时(1<=k<=len1),假设k=6

因为 k=6 ,<len1 && <len2,所以第六小的数只可能出现在两个数组的前六个数中。

所以我们只需调用求上中位数的函数,传入两个数组的前六位数即可

2.2 当10<k<15时(len1<k<len2),假设k=12

因为 k=12,所以 arr1 中全部数都有可能,数组 arr2 中,1(最大为第11个数),13-15(最小为13-15个数)不可能,所以满足条件的为 2-12 共11个数,而第一个数组为10个数,两个数组长度不同,不能调用函数,所以需要手动判断一个数,即 arr2 中的 2 

  • arr2[2] >=arr1[10]:arr[2]为第12个数
  • arr2[2] < arr1[10]:arr[2]最大为第11个数,不满足要求,淘汰,求解arr1[1-10],arr2[3-12]

求解出上中位数后(第十个)加上淘汰的两个,正好为第十二个数

2.3 当 15<=k<=25时(len2<=k),假设k=20

因为 k=20,所以arr2[10]之前的数都不满足要求(当arr1中全部元素全部压在arr2[10]之前,则arr2[10]能达到第20个数,之前的不满足要求),同理求出 arr1 中满足条件的,即

arr1[5]-arr1[10],arr2[10]-arr2[15],但只求出这两个数组的上中位数时会发现,之前淘汰掉了4+9=13个数,加上上中位数 6 =19,不是20,所以在求上中位数之前要先判断两个数组最左元素是否满足要求

  • arr1[5] >arr2[15]:返回arr1[5]
  • arr2[10]>arr1[10]:返回arr2[10]
  • 如果都不满足,则求解arr1[6]-arr1[10],arr2[11]-arr2[15]

这时,arr1 淘汰了5个数,arr2 淘汰了10个数,加上上中位数 5 正好为第20个数

3 Coding

	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;
		//k小于短数组长度
		if (kth <= s) {
			return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);
		}
		//k大于长数组长度
		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);
		}
		if (longs[kth - s - 1] >= shorts[s - 1]) {
			return longs[kth - s - 1];
		}
		return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
	}

	//求上中位数,要保证两个数组等长
	public static 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;
			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]);
	}

        

相关文章

JAVA数据类型的认识

一、JAVA是一种强类型的语言               强类型:在使用...

vue首屏优化方案

vue首屏优化方案

① 性能测试工具: Pingdom  Website Speed Test...

9.98万元起!“中国钢炮”吉利缤越COOL正式上市

9.98万元起!“中国钢炮”吉利缤越COOL正式上市

2022-08-09 20:17:47 8月9日,吉利汽车旗下“高智慧...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。