百度面试碰到一个问题

windoze

想了个算法
1、在A中取top K，复杂度O(Na * log(K))
2、在B中取top K，复杂度O(Nb * log(K))
3、对于每个top K中的An，加上top K中的Bn，对结果再取top K，复杂度O(K*K)
总共的时间复杂度是O(K * log(Na) + K * log(Nb) + K*K)，如果Na和Nb近似为N，整个算法的时间复杂度约为O(N*log(K) + K*K*)，如果K相对于N很小，则第二项可以忽略
第三步还有优化的空间，不过懒得想了。