2 qq 34119437 qq_34119437 于 2016.04.21 02:16 提问

Acm 一道数据结构的问题,求思路,不求代码。

假设我有两数组,分别有n1 n2个数据(每组数据都不相同)。我要两个数组中各取一个相加,有n1乘n2种结果,从小到大排,取前n个。(如果n1 n2 特别大怎么算),求大神教我。

7个回答

caozhy
caozhy   Ds   Rxr 2016.04.21 05:33

首先将n1 n2按照从小到大的顺序排成两列
最小的肯定是n1[0]+n2[0](下面简写,只用下标,比如n1[0]+n2[0]记作0,0)
稍微大一点的要么是1,0要么是0,1
如果是1,0,那么再大一点的,要么是1,1,要么是2,0
如果是0,1,那么再大一点的,要么是0,2,要么是1,1
也就是前一个最小值的下标左右各加1这两种可能之一
按照这个顺序找。

caozhy
caozhy   Ds   Rxr 2016.04.21 06:04

好像不对,需要回溯下

caozhy
caozhy   Ds   Rxr 2016.04.21 07:07

暂时保存下

 using System;
using System.Collections.Generic;
using System.Linq;

public class Test
{
    public static IEnumerable<int> foo(int[] a, int[] b)
    {
        /*
        a = a.OrderBy(z => z).ToArray();
        b = b.OrderBy(z => z).ToArray();
        int x = 0; int y = 0;
        while (x < a.Count() && y < b.Count())
        {
            Console.WriteLine("- {0} {1} {2} {3}", x, y, a[x], b[y]);
            yield return a[x] + b[y];
            if (x == a.Count() - 1) {y++; continue;}
            if (y == b.Count() - 1) {x++; continue;}
            if (a[x] + b[y + 1] < a[x + 1] + b[y])
                y++;
            else
                x++;
        }
        */
        a = a.OrderBy(z => z).ToArray();
        b = b.OrderBy(z => z).ToArray();
        int x = 0; int y = 0;
        while (x < a.Count() && y < b.Count())
        {
            Console.WriteLine("- {0} {1} {2} {3}", x, y, a[x], b[y]);
            yield return a[x] + b[y];
            if (x == a.Count() - 1) {y++; continue;}
            if (y == b.Count() - 1) {x++; continue;}
            if (a[x] + b[y + 1] < a[x + 1] + b[y])
                y++;
            else
                x++;
        }

    }
    public static void Main()
    {
        // your code goes here
        int[] a = {1,2,10,3};
        int[] b = {3,9,8,2,7};
        foreach (int i in foo(a, b))
            Console.WriteLine(i);
        //Console.WriteLine();
        //foreach (int i in (from c in a from d in b select c + d).OrderBy(x => x))
        //  Console.WriteLine(i);       
    }
}
u012949840
u012949840   2016.04.21 10:40

1.分别将两个数组排序,排序方法自选
2.设置一个数据长度为n的数组n3,使用向前搜索的插入法
3.两个数组长度分别为len1和len2,假设len1>len2,
用数组n1*n2 (一个嵌套循环),并向n3插入数据,插入成功返回1,否则返回0_
返回0的则break出内部的循环,为1则继续

第一层循环设置一个标记,记录n1中当前数据乘n2中所有的数时,只要有一个插入数组n3,则标记1,否则为0,
为0时,退出外层循环,此时的数组3中的数据就是那n个数,为1,则继续外层循环

智商不是很够,希望对你有所帮助

u012949840
u012949840   2016.04.21 10:46

两个数组中的数相加,,我看成乘了,大体还是一样的

u012949840
u012949840   2016.04.21 10:45

两个数组中的数相加,,我看成乘了,大体还是一样的

u012949840
u012949840   2016.04.21 10:46

两个数组中的数相加,,我看成乘了,大体还是一样的

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!