考一道数据结构+算法的题

xmubingo

sunyuanshuai 发表于 2011-9-30 19:38
sort the array A and array B descending;
for(i=0;i

我没看明白，你是不是应该禁用下编辑器代码。不然[ i ]都要变成斜体了

tangzk

xmubingo 发表于 2011-9-30 20:40
你的做法是先证明第m大的数一定落在m*m个元素以内

然后在m*m个元素里面找最大的前m个元素对吗？

是的，第m大的A*B的数，一定会落在排序后的前m*m个元素以内。
然后再借鉴归并排序的思路，依次取出前m个元素，无需全部计算m*m个乘法。

xmubingo

tangzk 发表于 2011-9-30 20:49
是的，第m大的A*B的数，一定会落在排序后的前m*m个元素以内。
然后再借鉴归并排序的思路，依次取出前m个 ...

我不太明白，采用归并排序怎么取得前m个最大值？为什么只要计算两次乘法

xmubingo

tangzk 发表于 2011-9-30 20:49
是的，第m大的A*B的数，一定会落在排序后的前m*m个元素以内。
然后再借鉴归并排序的思路，依次取出前m个 ...

我举个特例比如，排序之后：
A：3 3 2 1
B：3 3 2 1
我取前2个最大值应该是9和6.事实在如果你取3 3和3 3是无法取到的对吧。

tangzk

xmubingo 发表于 2011-9-30 21:11
我举个特例比如，排序之后：
A：3 3 2 1
B：3 3 2 1

发现归并排序的思路还是有些问题，虽然比较后生成的乘对还是能控制，但是比较麻烦。
如果再考虑这种特例，数值相同不算的话，那就直接将k=100时这100*100个乘对直接算出来，丢在极大堆里面，取前100个就好了，或者作top-100也可以，效率应该也远比O(M^2)要少得多的。
刚刚考虑问题不全面，汗！~

xmubingo

tangzk 发表于 2011-9-30 21:51
发现归并排序的思路还是有些问题，虽然比较后生成的乘对还是能控制，但是比较麻烦。
如果再考虑这种特 ...

是啊，关键是复杂度不能超过k^2。你想啊，算k*k个乘积需要(k-1)*k/2个时间，相当于还是k^2

简单点，我们还是考虑题目的要求。
每个数组m个元素，取两个数组乘积的前m个最大值。要求复杂度小于m^2。

tangzk

xmubingo 发表于 2011-9-30 22:11
是啊，关键是复杂度不是M^2, 是k^2。你想啊，算k*k个乘积需要(k-1)*k/2个时间，相当于还是k^2

当M>>K的时候，这优势还是可观的呢。
嘿嘿，找线性时间的话，还要多思考，尤其是各位擅长数学的同门们。
我数学太菜了，

xmubingo

tangzk 发表于 2011-9-30 22:16
当M>>K的时候，这优势还是可观的呢。
嘿嘿，找线性时间的话，还要多思考，尤其是各位擅长数学的同门们。 ...

对方给的提示做法是用堆做的。只是我还没想到怎么个做法能使复杂度小于m^2。

Freshines

讲个思路吧，
先对两个数组分别排序，这样就可得到可能的最大和最小乘积MAX,MIN。
对MIN~MAX范围进行二分枚举，举个例：
1、假设当前枚举到的值为MID;
2、对于A[i], 可得到商D=MID/A[i], 用D到B中进行二分查找合适位置，这样就可以知道A[i]*B[j](j{0,m-1})时中大于MID的个数cnt，
3、重复2，循环i,相加每个cnt,最后的和即是当前MID的最终排名L
4、根据L与要找的K比较结果，确定下一个MID的范围[MIN, MID] OR [MID+1, MAX]，得到MID，重复1直到L==K.


注:因为结果里面有相同的值，所以在对B进行二分查找合适位置，需要对找到的合适位置的前后进行进一步比较。

复杂度: m*log(MAX)*log(m)

二分枚举MID,O(log(MAX))，最大64
枚举A[i], O(m)
二分查找B, O(logm)

xmubingo

sunyuanshuai 发表于 2011-9-30 19:38
[ 本帖最后由 sunyuanshuai 于 2011-10-1 13:11 编辑 ]

sort the array A and array B descending;

这个时间复杂度是多少？