机器学习和生物信息学实验室联盟

标题: 考一道数据结构+算法的题 [打印本页]

作者: xmubingo 时间: 2011-9-30 17:31
标题: 考一道数据结构+算法的题
[ 本帖最后由 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 时间: 2011-9-30 18:01
本帖最后由 sunyuanshuai 于 2011-9-30 18:13 编辑

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

作者: xmubingo 时间: 2011-9-30 18:03

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

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

作者: xmubingo 时间: 2011-9-30 18:08

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 时间: 2011-9-30 18:15
不是使用我的意思是去这前100个分别与另一个数组的元素相乘，然后取前100个

作者: xmubingo 时间: 2011-9-30 18:35

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

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

作者: tangzk 时间: 2011-9-30 18:58
本帖最后由 tangzk 于 2011-9-30 18:59 编辑

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 时间: 2011-9-30 19:38
[ 本帖最后由 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 时间: 2011-9-30 19:47

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

分析的很好，顶一下

作者: xmubingo 时间: 2011-9-30 20:40

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

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

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

作者: xmubingo 时间: 2011-9-30 20:42
本帖最后由 xmubingo 于 2011-9-30 20:43 编辑

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

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

作者: tangzk 时间: 2011-9-30 20:49

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

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

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

作者: xmubingo 时间: 2011-9-30 21:03

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

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

作者: xmubingo 时间: 2011-9-30 21:11

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 时间: 2011-9-30 21:51
本帖最后由 tangzk 于 2011-9-30 21:51 编辑

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 时间: 2011-9-30 22:11
本帖最后由 xmubingo 于 2011-9-30 22:22 编辑

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

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

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

作者: tangzk 时间: 2011-9-30 22:16

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

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

作者: xmubingo 时间: 2011-9-30 22:21

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

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

作者: Freshines 时间: 2011-10-1 13:19
讲个思路吧，
先对两个数组分别排序，这样就可得到可能的最大和最小乘积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 时间: 2011-10-1 14:17

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

sort the array A and array B descending;

这个时间复杂度是多少？

作者: xmubingo 时间: 2011-10-1 14:32

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

sort the array A and array B descending;

9 1 1 1 1
5 4 3 2 1

用你的做法试试

作者: xmubingo 时间: 2011-10-1 15:42
本帖最后由 xmubingo 于 2011-10-1 15:42 编辑

Freshines 发表于 2011-10-1 13:19
讲个思路吧，
先对两个数组分别排序，这样就可得到可能的最大和最小乘积MAX,MIN。
对MIN~MAX范围进行二分 ...

看懂了，但是这里不太清除。

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

为什么最大是64？而且你的时间复杂度是和MAX相关，要是我的MAX和m有关怎么办

作者: fiona 时间: 2011-10-1 15:50
先对数组A,B降序排序，排序后A,B使用链表存储link_A,link_B
数组element用于存放A[i]*B[j]的前m大元素，初始化为0
while A,B链表都不为空
   数组new_element用于存放A[i]*B[j]的值；
   1. 从link_A中取第一个元素X，指针p指向link_B中的第一个元素；
   2. 从B中取出p指针指向的元素Y，如果X*Y>element[m-1]，就将X*Y的值放入new_element中，p指向下一个元素，循环步骤2；否则，执行步骤3；
   3. 将p指针所指元素及其之后的元素删除
   4. 将数组element，new_element的元素合并起来进行排序，重新得到前m个元素，更新element数组；
5.将X从link_A中删除；

   if A,B链表都不为空
      数组new_element用于存放A[i]*B[j]的值；
   1. 从link_B中取第一个元素X，指针p指向link_A中的第一个元素；
   2. 从A中取出p指针指向的元素Y，如果X*Y>element[m-1]，就将X*Y的值放入new_element中，p指向下一个元素，循环步骤2；否则，执行步骤3；
   3. 将p指针所指元素及其之后的元素删除
   4. 将数组element，new_element的元素合并起来进行排序，重新得到前m个元素，更新element数组；
   5. 将X从link_B中删除；

作者: xmubingo 时间: 2011-10-1 16:11

fiona 发表于 2011-10-1 15:50
先对数组A,B降序排序，排序后A,B使用链表存储link_A,link_B
数组element用于存放A*B[j]的前m大元素，初始化 ...

我明白你的意思，举个例子：

A: 8 7 6 5 4
B: 8 7 6 5 4

首先，取A中的8开始和B中的每个元素相乘，得到64 56 48 40 32 这五个值放入容器中，其中最小值是32。删除A中的8，则A: 7 6 5 4

然后，取B中的8开始和A中的每个元素相乘，得到 56 48 40 32这四个值，由于32<=容器中的最小值，因而，将A中的4删除，同时，删除B中的8。则：A: 7 6 5, B: 7 6 5 4。将56 48 40和容器中的5个值排序，取最大的前5个放回容器中。容器中: 64 56 48 40 32

接着，取A中的7开始和B中的每个元素相乘，得到 49 42 34 28, 由于28<=容器中的最小值，因而将B中的4删除，同时，删除A中的7。则： A: 6 5，B: 7 6 5。将49 42 34和容器中的5个值排序，取最大的前5个放回容器中。容器中: 64 56 49 48 42.

最后，取B中的7开始和A中的每个元素相乘，当发现7乘以A中的最大值6等于容器中的最小值，因而，删除A中6以及之后的所有值，到此，A变为空，计算结束。容器中: 64 56 49 48 42.

作者: fiona 时间: 2011-10-1 16:40

zouquan 发表于 2011-10-1 16:27
Step 1 Sort A and B, get C and D
Step 2 int i=1,j=1,num=0;
while num

好吧，是m*m

作者: zouquan 时间: 2011-10-1 17:52

fiona 发表于 2011-10-1 16:40
好吧，是m*m

之前的算法错了，确实挺恶心。

不过有排序时间复杂度的算法是没问题的，我懒得写了

作者: YuHaiyang 时间: 2011-10-5 17:27
我也来说说我的想法吧
两边的数组建个堆，但不用排序，最坏复杂度Mlog(M)，因为只是建堆，从而估计还要小一点
然后面对两个堆A,B，写个函数XX，输入分别为两个堆的一个node，分别从A,B最大点开始，计算乘积，所得乘积放入一个M大小的有序数组中（链表也行，各有各的好出），同时把着两个点的位置记录下来（建个类或结构体就行，和数值放一起），每次找数组中最大值对应的两个堆节点的位置，然后分别用这两节点乘以对方子结点，乘积加入排序数组中，如果满了就把多余M个的尾巴截掉。然后从第一个数（即两个堆的第一个节点）开始，因为父节点必定大于等于子结点，所以函数XX所得到的4个乘积必定小于等于现在所选的数，即从第一个点扫到第M大的点不用回头，而函数运行一次就计算4次计算，所以这个判断为4次运算。复杂度也就4*M次、
从而整个算法最花时间也就开始的建堆，维Mlog(M)

作者: zjcdm 时间: 2014-5-5 21:59
采用双二分，先对两个数组按降序排列，两两相乘的值在a[0]*b[0] 和a[n-1]*b[n-1]之间，n为数组长度
mid_mul=(a[0]*b[0] +a[n-1]*b[n-1])/2, 这样我们只要验证a[i]*b[j] >= mid_mul 的个数为n个就行。这里的时间复杂度是O(log(max) ) ，  max=a[0]*b[0]
验证部分是固定数组a，对b二分，统计a[i]*b[j] >= mid_mul 的个数。这里的时间复杂度是O(n*log(n))

总的时间复杂度是 O(n*log(n)*log(max) ) ，max=a[0]*b[0]。当n很大的时候小于 O(n^2)

代码：
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

int a[1024], b[1024], n, c[1024], index = 0;

int calc(int x, int v)
{
if (x * b[0] < v)
      return 0;

int l = 0, r = n - 1, mid;

while (l < r)
{
      mid = ((l + r) >> 1) + 1;

      if (x * b[mid] >= v)
         l = mid;
      else
         r = mid - 1;
}
return l + 1;
}

void calc2(int x, int v, int& tot)
{
if (x * b[0] < v)
      return;

int l = 0, r = n - 1, mid;

while (l < r)
{
      mid = ((l + r) >> 1) + 1;

      if (x * b[mid] > v)
         l = mid;
      else
         r = mid - 1;
}

for (r = 0; r <= l; r++)
{
      //printf("%d\n", x * b[r]);
      c[index] = x * b[r];
      index ++;
}
tot += l + 1;
}

int main()
{
int i, j, l, r, mid, num;
scanf("%d", &n);//数组长度
for (i = 0; i < n; i++)
{
      scanf("%d", &a[i]);
}

for (i = 0; i < n; i++)
{
      scanf("%d", &b[i]);
}

sort(b, b + n, greater<int>());
sort(a, a + n, greater<int>());

l = a[n - 1] * b[n - 1];
r = a[0] * b[0];

while (l < r)
{
      mid = ((l + r) >> 1) + 1;

      num = 0;
      for (j = 0; j < n; j++)
      {
         num += calc(a[j], mid);
      }

      if (num >= n)
         l = mid;
      else
         r = mid - 1;
}

int tot = 0;
for (i = 0; i < n; i++)
{
      calc2(a[i], l, tot);
}

sort(c, c + index, greater<int>());

for(i = 0; i < index; i++)
{
      printf("%d\n", c[i]);
}
for (; tot < n; tot++)
{
         printf("%d\n", l);
}

return 0;
}

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)