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

xmubingo

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

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

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

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

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

fiona

先对数组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

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

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

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

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

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

YuHaiyang

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

zjcdm

采用双二分，先对两个数组按降序排列，两两相乘的值在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;
}