标签（空格分隔）： 数据结构与算法
题目:
任意给定两个已经排好序的数组A和B,求出A与B合并后第K大的值.
int A[] = {15, 10, 9, 8, 6, 5, 3, 1};
int B[] = {14, 13, 12, 11, 8, 7, 4, 2};
targe k = 6 ; result = 10;
分析:
我们可以利用并归排序的思想分别从A和B中取出一个值进行比较,同时,然后用一个引用计数记录目前找到了第i大的值,当i= k时,就找到了.显然,这种方式,当k = 最小的时候,我们将两个数组全部遍历,因此时间复杂度O(m+n)
有没有更好的方式呢?
上面的一种方式,我们分别从A,B中一个一个的取出元素,直到找到了第k大的元素,由于A,B都是已经排好序的,我们是不是可以利用这一点呢?
我们假设A,B的长度都大于k/2,我们比较A[k/2-1]与B[k/2-1]的大小:
- A[k/2-1] < B[k/2-1] :
B数组中从B[0]到B[k/2-1]肯定比合并之后第K大元素的值都要大,也就是说,B中前k/2个元素肯定是合并之后数组中的前k大元素.于是我们可以将这k/2个去掉,这样问题,就化解成了求解第k-(k/2)大的元素了.- A[k/2-1] > B[k/2-1] ,原理和上面一样我们将
A中的前k/2个元素移除.- A[k/2-1] = B[k/2-1] ,表示我们找到了第
K大的元素,我们第k大的元素是A[k/2-1]或者B[k/2-1]任意一个.
因此我们可以使用一个递归实现:
int find_kth(int *A , int m ,int *B ,int n ,int k){
//两个数组总是有长有短,我们总是让m <= n的
if(m> n){
return find_kth(B,n,A,m,k);
}
//我们不断的截断数组,最后,小的那个数组,则会最先出现0
if(m == 0){//最小的数组是空的,寻找第k大的元素,就只能从B数组中寻找了
return *(B+k-1);
}
//当我们在不断的截取数组时,其实我们的k也在不断的减少,假设我们的k = 10;
//当我们从A B中排除5个比Arr[k]大的元素时,剩下的任务就是,寻找 k = 5;
//因为我们已经去处了5个比Arr[k]大的元素,此时这个元素就是第k-5大
//当程序不断的进行,结果k =1
if(k == 1){
return max(*A,*B);
}
//以上就是递归终止的条件
//开始拆分
//我们利用的原理是:两个数组分别从大到小拍好了顺序,B数组的第三个比,A数组的第三个要大,则这个则B数组的这三个
//数肯定排在前6名,因此我们可以删除掉这三个数据
int offset = min(k/2,m);
if(*(A+offset-1) < *(B +offset -1)){
return find_kth(A , m , B+offset, n-offset, k - offset);
}else if(*(A+offset-1) > *(B +offset -1)){
return find_kth(A+offset , m-offset , B, n, k - offset);
}else {
return *(A+offset-1);
}
}
