问题描述

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

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

解决方案

首先将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这两种可能之一
按照这个顺序找。

解决方案二：

好像不对，需要回溯下

解决方案三：

暂时保存下

 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);
    }
}

解决方案四：

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，则继续外层循环

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

解决方案五：

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

解决方案六：

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

解决方案七：

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