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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
ACM-汽水瓶(C语言基础题)
描述 有这样一道智力题:“某商店规定:三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶,她最多可以换多少瓶汽水喝?”答案是5瓶,方法如下:先用9个空瓶子换3瓶汽水,喝掉3瓶满的,喝完以后4个空瓶子,用3个再换一瓶,喝掉这瓶满的,这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水,喝掉这瓶满的,喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶,最多可以换多少瓶汽水喝? 输入输
部分acm题目的解题思路(转)
Problem 1346 - Exchange 用棋盘多项式和数论中的扩展欧几里德来做. 根据题意可以构造一个棋盘,用阴影代表禁区,可得到禁区都是分开的正方形n*n..n*n正方形小格子禁区的棋盘多项式为 f(n)=,m[110]存各学校的人数,n表示学校数,总人数为s,那么大棋盘多项式为f[m[0]]*f[m[1]]*...*f[m[n-1]];然后用一个数组xishu[10001]存多项
数据结构(C语言版)”栈与队列“章节迷宫求解问题的思路与实现
迷宫求解问题来源自”数据结构(C语言版)“一书第50页的例题。该例题要求在不使用递归(因为暂时还没讲到),只能通过使用诸如入栈出栈的方式获取一条可以走出迷宫的路径。     在看完文字提示后,我就没有看后面的伪代码实现了(对于我来说,本书的所有伪代码的组织就像一团乱麻,反而更加没有头绪)。在理解文字说明的基础上我试图通过独立思考解决,以下就是我的思考过程。 1.迷宫求解问题的规则有哪些?
邮局选址代码及详细分析
关于acm题目中邮局选址问题的详细代码、数据结构和解题思路的分析
数据结构:栈和队列-迷宫问题求解
//--------------------文件名:Maze.cpp------------------------//----------------------By SunxySong-------------------------//说明:本程序以迷宫问题进行演示,了解栈和链表的数据结构.//运行过程:随机生成迷宫地图(由于未详细设计算法,故地图较简单),//         并演示找到出
数据结构和算法设计(迷宫求解问题的栈和队列的实现)
此问题中,迷宫用一个二位数组data[ ][ ]表示,data[i][j]的值为0,则表示该点为通路;如果为1,则表示该点为障碍;如果为-1,则表示该点已经走过。数组的四周值都为1,表示边界。给定起点和终点,求起点到终点的路径。 可以使用栈对二维数组进行深度优先搜索,直到找到终
DP思路解算法题
今天首次接触到DP算法,DP是dynamic programming的缩写,中文为动态规划编程,是一种编程思想。 LeetCode上这么一道题: Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb",
数据结构经典问题——出栈顺序
对于数据结构的问题,如果思路稍有不对,就容易陷入逻辑混乱。我希望自己对数据结构的理解,能够给大家一点帮助。我会将所有我有过心得的问题在我的博客上写出来,欢迎大家浏览,如果有什么不对的地方,还请大家指正,有问题可以给我留言,我会尽量解决,谢谢。 声明一下我写博客的初衷:不是炫耀,而是回报。因为我在计算机方面的知识好多都从网上找到答案,因此我也 将自己搜寻整理的材料,自己写的材料,展示到网
图论的遍历 之 欧拉回路
图G的一个回路,若它通过G的meiyitioa
acm-一个简单的数学题
一个简单的数学题 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 zyc最近迷上了数学,一天,dj想出了一道数学题来难住他。算出1/n,但zyc一时答不上来希望大家能编程帮助他。 输入 第一行整数T,表示测试组数。后面T行,每行一个整数 n (1 输出 输出1/n. (是循环小数的,只输出第一个循环节). 样例输入 4 2 3 7 1