百度面试碰到一个问题

快乐的土豆

windoze 发表于 2014-05-18 01:28
想了个算法
1、在A中取top K，复杂度O(Na * log(K))
2、在B中取top K，复杂度O(Nb * log(K))

假设分别对 A,B降序排列后形成 A'[1..n], B'[1..n]，
那么很显然，
最大的数是A'[1]+B'[1],
第二大是Max( (A'[1]+B'[2]),  ( A'[2]+B'[1])),
第三大，如果 A'[1]+B'[2] > A'[2]+B'[1], 则 Max( (A'[1]+B'[3]), (A'[2]+B'[1])),
           否则                                            Max( (A'[1]+B'[2]), (A'[3]+B'[1])),
依次类推，

事实上，我们并不需要对A,B排序，甚至最多只需要取出某一方的Top(K)，算法复杂度就是Top(K)的复杂度。

w359405949

A 3,2,1 B 4,2,3

0，最大和最小是特例，可以在排序后直接获得，这里只给出求[2, k-1]的O(nlogn)算法

1，分别排序
A 3,2,1 B 4,3,2

2，分别求数组中每个元素相对于该组最大数的差值
A 0,1,2 B 0,1,2

3，以2中求取出来的差值将两个数组的数排序得数组C，并标记为数组A还是数组B，两个组最大的数不纳入排序
C 2(A, 1) 3(B, 1) 1(A, 2) 2(B, 2)

4，取K个最大，那么就从C中依次取值，并与相对的数组最大值相加，那就是第K个最大数的值。
例：
k = 2
2(A, 1) + 4(B) = 6
k = 3
3(B, 1) + 3(A) = 6
k = 4
1(A, 2) + 4(B) = 5
k = 5
2(B, 2) + 3(A) = 5

得：[2, k - 1]的顺序为 6, 6, 5, 5 （相同解可合并可不合并）

算法复杂度为：
快排（步骤1）O(nlog n) + 分别求值（步骤2）O（n) + 合并排序（步骤3）O(n) + 取值 (步骤4）O(k) = n log n （算法总时间取决于排序的时间复杂度）

===
上次把快排的时间复杂度记错了，这里做修正。

lwhjava

时间复杂度