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

xmubingo

[ 本帖最后由 xmubingo 于 2011-10-1 16:46 编辑 ]

有两个正数数组 A和B
A[1], A[2], A[3],..., A[m]；m很大
B[1], B[2], B[3],..., B[m]

取数组A里面的一个数A[i]乘以数组B里面的一个数B[j]，会得到一个乘积 A [i]* B[j]

这样一共可以得到m^2个乘积结果，当然结果里面有相同的值。

求一个计算方法，使得快速找到m^2个结果中的最大m个结果。要求时间复杂度小于O(m^2)。

sunyuanshuai

A数组和B数组中的元素之有没有范围，我的思路是找到A数组和B数组的前100个最大的

xmubingo

sunyuanshuai 发表于 2011-9-30 18:01
A数组和B数组中的元素之有没有范围，我的思路是找到A数组和B数组的前10个最大的

你再想想这样确定会找到最大的前100个么

xmubingo

sunyuanshuai 发表于 2011-9-30 18:01
A数组和B数组中的元素之有没有范围，我的思路是找到A数组和B数组的前10个最大的

举个例子
A: 9 8 7 6
B: 5 4 3 2
取乘积中的前四个最大值，你取9 8和5 4,显然是不对的。

sunyuanshuai

不是使用我的意思是去这前100个分别与另一个数组的元素相乘，然后取前100个

xmubingo

sunyuanshuai 发表于 2011-9-30 18:15
不是使用我的意思是去这前100个分别与另一个数组的元素相乘，然后取前100个

我有个地方没有修正，是取最大m个结果

tangzk

xmubingo 发表于 2011-9-30 18:08
举个例子
A: 9 8 7 6
B: 5 4 3 2

应该来说各自取K个最大元素的方法是可行的。
各个数组里面取最大的100个元素，交叉相乘，取出100个最大的。
验证不会有前100的元素落在这100*100个元素之外，最大的元素自然是A[1]*B[1]，这里假定已经把A[]和B[]按从大到小非递减有序，这样第2大的元素可能是A[1]*B[2]，也可能是A[2]*B[1]，再接下来可能是A[1]*B[3]，A[2]*B[2]和A[3]*B[1]，这完全就是合并排序的思路了，那么对于A[i ]*B[j]，第100最大的元素会有条件i+j-1=100，而对于i,j，有条件i>=1 && j>=1，所以即使取i=100，j=1或相反，亦能满足该条件。因此，不会有第K(K<=100)的数落在这100*100之外。
当然，实际上这里按照合并排序的思路，并不需要计算100*100的所有数据，只需要计算前面100个，每次计算2次乘法即可。
所以效率可以为：O(Mlog(2*100)+Mlog(2*100)+2*100)，其中Mlog(2*100)为Top-100的时间复杂度。

欢迎板砖！

sunyuanshuai

[ 本帖最后由 sunyuanshuai 于 2011-10-1 13:11 编辑 ]

sort the array A and array B descending;
for(i=0;i<L(A);i++)
{
  como=A[i]*B[i];
  for(j=0;j<i;j++)
  {
    put A[i]*B[j] into the temporary array1;
    put A[j]*B[i] into the temporary array1;
  }
  sort the array1 descending;
  put the elements which is bigger than como into target array tarray;
  put the como into the tarray;
  the last two step must check the length of tarray , if it is equal to m ,then end program;
}
output the elements into the target array tarray.

sunyuanshuai

tangzk 发表于 2011-9-30 18:58
应该来说各自取K个最大元素的方法是可行的。
各个数组里面取最大的100个元素，交叉相乘，取出100个最大 ...

分析的很好，顶一下

xmubingo

tangzk 发表于 2011-9-30 18:58
应该来说各自取K个最大元素的方法是可行的。
各个数组里面取最大的100个元素，交叉相乘，取出100个最大 ...

你的做法是先证明第m大的数一定落在m*m个元素以内

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