By

文章目录
  1. 1. 题目
  2. 2. 解析

题目

在两个有序数组中，找到第k大的数字，要求复杂度为O(log(m+n))

解析

因为题目是要求复杂度O(log(m+n))，则无法直接使用遍历，重排的方式了，基本一下子就能想到类似二分查找的方法

假设这两个数组分别为A和B

  1. 假如两个数组分别取k/2位置的值，如果A[k/2-1]等于B[k/2-1]，则这个值就是第k大的数
  2. 但是如果A[k/2-1]大于B[k/2-1]，则B[0:k/2-1]范围内的值都将会小于第k大，这里的值可以直接过滤，从B[k/2]再开始查找
  3. 如果A[k/2-1]小于B[k/2-1]同理2的方式
  4. 因此可以根据k/2部分值大的大小比较进行递归

同时在递归时会预见某个子数组会0长度或者k到1的边界，此时直接取值返回即可，因此对应的代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
using namespace std;

int binary_find_k(int* A,int len1,int* B,int len2,int k){
	if(len1>len2)
		// 需要保证A数组比B短
		return binary_find_k(B,len2,A,len1,k);
	if(len1 == 0)
		return B[k-1];
	if(k==1)
		return min(A[0],B[0]);

	int k1 = min(k/2,len1);
	int k2 = k-k1;

	cout << k1 << " , " << k2 << ":" <<  A[k1-1] << " , "<<B[k2-1] <<endl;
	if(A[k1-1] > B[k2-1]){
		// 说明B[0:k2-1]部分都会比   第k大 数字要小，这部分抛弃，继续递归
		cout << "keep k1" << endl;
		return binary_find_k(A,len1,B+k2,len2-k2,k1);
	}else if(A[k1-1] < B[k2-1]){
		cout << "keep k2" << endl;
		return binary_find_k(A+k1,len1-k1,B,len2,k2);
	}else{
		// 这个就是k大
		return B[k2-1];
	}
}

int main(){
	int A[] = {2,3,4,7,8,12};
	int B[] = {1,5,6,8,10,11};
	int len1 = 6;
	int len2 = 7;
	int k = 5;
	cout << binary_find_k(A,len1,B,len2,k)<<endl;

	
	return 0;
}

这里正好也输出为5

文章目录
  1. 1. 题目
  2. 2. 解析