Java算法设计:迭代器实现排序(求各位大佬各抒己见) 80C

老师预留的习题,说可能会考。希望能得到比较准备的回答用以备考。

假设你有M个迭代器(Java.util.Iterator),其中每一个迭代器定义为:由多个低成本基础迭代器组成,形成一个迭代器链(chain of Iterator),我们称之为resultant Iterator。每个resultant Iterator传递一个有序数据流。我们需要将这些数据流合并成一个最终有序数据流。

数据:每个数据由一串K个Key的序列组成 [k1,k2,k3,…,kK]
数据排序的规则为:最先排列k1,其次k2再次k3,……例如 [2,3,1,…] > [2,1,3,…] > [1,3,2,…]。每种key的排列在一个resultant Iterator中只会出现一次,但是多个resultant Iterator中可能出现相同的排列。

  • 问题A:为了便于分析,我们假设每个resultant Iterator返回N个元素,设计一种算法,能得到最终有序数据流,同时效率高于 O(N.M.K.lg(M)). 并且计算所设计算法的复杂度。(可以设计你需要的变量和参数)。如果有多种算法,请简述各自的优劣。

  • 问题B:简述如何重新设计迭代器,可以降低计算成本。为什么?

  • 问题C:若要在数据库中存储不可变的有序数据集(如本题中的数据),什么数据结构最为合适,为什么?若本题数据中所有的key都可以在byte的量级进行排序,例如有2个key,他们的排序根据他们第一个不同的byte进行排序。那对我们之前选择的数据结构有影响吗?若只有部分key可以又会怎么样?

  • 问题D:基于Java的思想,如何优化它在内存中的表示。为什么?

2个回答

如果你每个迭代器都是有序的,那么连起来就是归并排序。然后就是如果你的比较操作也花费成本,就要实现hash算法。
内存和数据库(文件系统)优化的方式不同,因为内存是随机访问的,可以考虑使用最小堆。数据库可以用排序索引。

讲道理,我没有读懂你数据和数据排序规则

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
数据结构算法设计: 请设计一个算法,统计一个循环单链表L中的结点个数。

算法设计: 请设计一个算法,统计一个循环单链表L中的结点个数。

求Java高效合理排序算法

安卓界面列表可任意拖拽变换列表数据顺序,保存数据在后端服务,怎样在后端实现排序,求各路高手指点,确切的方案也可以,大概思路方向也可以,希望大家不吝赐教,先谢过

JAVA实现距离矢量算法

1.编程实现右图所示简单网络拓扑的距离向量路由算法。 1.1 结点之间的连接关系固定; 1.2 链路开销可以由用户设定。 2.距离向量算法的实现方式: 2.1 可以利用多线程机制;每个结点一个 线程;每隔一段事件利用线程间通信 机制传递距离向量(DV);或是 2.2 每个结点利用单独的进程实现;每隔一 段时间利用Socket实现结点间的距离向量交换; 2.3 距离向量的计算与结点路由表的显示。 3.网络拓扑结构的描述(数据结构),拓扑结构利用文件存储。 4.结点初始化流程/消息传递与路由计算/节点路由表显示等的程序设计 我总共有40个金币,做出来了,我都给你,求大牛

求助Java算法,这两个算法问题有Java代码实现

1. 从N个元素集合里面随机抽取M个元素(M<N)。 C/C++: void randomChoose(int*data, intn, int *result, int m); Java: void randomChoose(int data[], int result[]); 说明: 1.Data是待抽取的元素集合,n是data的长度,result是抽取的结果,m是结果集的长度。 2.同一个元素不能被反复抽取。 3.每个元素被抽取到的概率必须相同。 4.不需要自己写随机函数,C版本中允许使用rand()函数,java版本中允许使用Random对象 5.算法效率尽可能高 6.必须要有代码注释和算法说明。 例如:data里面的数据是{3, 4, 9}。n = 3, m = 2。此时result的可能输出结果有{3, 4},{3, 9},{4, 9},{4,3},{9, 3},{9, 4},每种可能的输出概率相同。 2.交换链表的奇偶顺序 函数说明: swap函数交换链表第2i和第2i+1个元素(如果都有的话),并返回交换之后的链表。 示例: 交换前链表的顺序 交换后链表的顺序 1→2→3→4→5 ==> 2→1→4→3→5 1 ==> 1 (链表仅含一个元素) 1→2 ==> 2→1 ==> (链表为空) C/C++: 链表节点定义为: struct node { struct node *next; … }; struct node *swap(struct node *list); Java: 链表节点定义为: class Node { public Node next; … } Node swap(Node list) 注意点和要求如下: 0. swap函数返回新的链表指针 1. swap函数要求对节点的指针/引用进行操作(不得创建任何新的链表节点) 2. 不得使用任何库函数/API,如需使用类似功能, 请自行实现 3. 不得将链表转化为其他类型数据结构再进行交换,如数组等

java语言中哪一种排序算法用的最多?

java语言中哪一种排序算法用的最多?快速排序既然效率高,为什么我们还要用冒泡呢?冒泡的好处是什么?

java程序设计(字符串排序)

用main方法排序(按首字母或按字符串长度) 要求: ①输出原数组和排序后的数组 ②若有“,”“.”不能进行排序, 并将不符合排序要求的数组打印出来 ③不能用API,可用选择、冒泡、快速

求一个Java实现的卡尔曼滤波算法

现在做一个无线的定位系统,求一个Java实现的卡尔曼滤波算法

既然java语言提供了排序算法的封装,为什么我们还要自己写冒泡

一个关于排序的问题:既然java语言提供了排序算法的封装,为什么我们还要自己写冒泡排序?什么时候用到冒泡排序?

java最优组合算法问题,编程实现字母最优组合生成最优解

要求:输入A~K中的任意几个字母(无重复),对这些字母进行组合。输出最优组合的最小组数n和组合方案,使用java语言。 约束条件:A可以和B一组; A可以和E、F、G一组; C、D、H要单独分组; I可以和E、F、G一组; J可以和E、F、G一组; K可以和E、F、G一组; 如果可以,希望用退火算法的思想来解决本问题。毕设赶着要用这个算法,希望尽快提供解决方案,拜谢!

求一个抽奖算法,最好java实现

需求如下: 总共分四等奖, 1等奖名额2个,中奖概率2/10000 2等奖名额10个,中奖概率5/1000 3等奖名额100个,中奖概率10/100 4等奖名额880个,中奖概率25/100 求一个算法,算出用户单次抽奖中奖等级(1,2,3,3等奖或不中奖)。 最好java实现。

java实现分组最少重复算法

有这样一个需求: 固定N个元素,分M组(N是M的整数倍), 每个元素只能分进一个组里,且每个组人数相同,保证每轮每组重复的元素最少,输出每次分组明细; 比如 {1,2,3,4,5,6,7,8,9,10,11,12},分四组,分三轮。则结果为 {1,2,3}{4,5,6}{7,8,9}{10,11,12} {1,4,7}{2,5,10}{3,8,11}{6,9,12} {1,5,12}{2,4,9}{3,8,10}{6,7,11} java c++ 都可

Edmonds算法:最大权匹配的java实现

最近帮忙做一个课题任务,要求用java实现Edmonds算法。 Edmonds算法的具体描述可以参阅百度文库的这篇文章: http://wenku.baidu.com/link?url=GVU282p9OTXuMPlFUy4eb_a_j-t2TO8HsHEh-rzPo0_y6txgB6jCuNGwBfhhWA1i87mrInc31Z4pIGp1mPPCJGCwPKLOcfpvLqz7_7QnFmS 要求输入:图的节点和带权边 要求输出:边的最大匹配,用List表示 就算没有程序,只有思路也是欢迎的。 我自己的没有太多时间做这个,希望各位大神不吝赐教。

串模式匹配BF算法的java实现

如下代码,进行串模式匹配BF算法的java实现 ``` class BF{ public int bF(char S[],char T[]){ int i=0,j=0,index=0; while(S[i]!='\0'&&T[j]!='\0'){ if(S[i] == T[j]){ i++; j++; }else{ index++; i = index; j = 0; } } if(T[j]!='\0'){ return index+1; }else{ return 0; } } } public class String_matching { public static void main(String[] args) { BF bf = new BF(); String str1 = "ababacbc"; String str2 = "bacb"; char c1[] = str1.toCharArray(); char c2[] = str2.toCharArray(); bf.bF(c1, c2); } } ``` 运行后抛出如下异常 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4 at BF.bF(String_matching.java:4) at String_matching.main(String_matching.java:28) 请问这是为什么?谢谢

php自带的sort排序和用php实现排序算法的性能比较?

我今天特地试验了一下两者的性能 php自带的排序函数 100000的数据 排序 平均耗时0.068s ``` for ($i = 0; $i<100000;$i++){ $arr[] = rand(0,10000); } $t1 = microtime(true); sort($arr); $t2 = microtime(true); echo "php自带排序sort()耗时:".($t2-$t1); ``` 自己写的快速排序 平均耗时1.0s ``` for ($i = 0; $i<100000;$i++){ $arr[] = rand(0,100000); } $t1 = microtime(true); $returnAr = quickSort($arr); $t2 = microtime(true); echo "快速排序耗时:".($t2-$t1); //快速排序 function quickSort($arr) { //先判断是否需要继续进行 $length = count($arr); if($length <= 1) { return $arr; } //选择第一个元素作为基准 $base_num = $arr[0]; //遍历除了标尺外的所有元素,按照大小关系放入两个数组内 //初始化两个数组 $left_array = array(); //小于基准的 $right_array = array(); //大于基准的 for($i=1; $i<$length; $i++) { if($base_num > $arr[$i]) { //放入左边数组 $left_array[] = $arr[$i]; } else { //放入右边 $right_array[] = $arr[$i]; } } //再分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数 $left_array = quickSort($left_array); $right_array = quickSort($right_array); //合并 return array_merge($left_array, array($base_num), $right_array); } ``` 明显是php自带的函数排序速度快很多。 但重点是,为什么还有那么多问题是问 如何用php实现快速排序等算法?

JAVA算法,求最优平均算法。尽可能平均

题目: 现有大约1000个左右催收单,需要发给20个左右催收员。每个催收单的金额不同要求对每个催收员分配到的催收单,尽可能的在金额上都比较平均。金额涉及到奖金,不能不公平处理 要求: 写出实现方法、单元测试代码 例如 30 20 30 20 20 分成 2组 1。30 30 2。20 20 20 分成三组 1。30 2。20 20 3。20 30

谁有力导向布局或其他自动化布局算法的java实现源码

在研究数据可视化,看到了很多的框架可以实现自动化布局算法,寻找可视化布局算法的java实现完整版(力导向布局算法或是其他的自动化布局算法),或实现的理论,千万别只留下一个数学公式,对数学的研究不够!!!!

求java实现作业查重实现思路或者算法?

描述:是很多同学交上来的作业是抄袭其他同学的。 要求:我要完成的程序就是找出类似的作业。并把他们雷同的内容用高亮的文字显示出来,作为抄袭证据。希望能得到写思路,现在脑袋一片模糊,或者给些资料。谢谢!!!

求:Java实现下面的算法,要求尽量高的性能

算法要求:把下面两个list: columnNames list: ["Comment", "Comment", "Cost", "Term", "Cost"] columnValues list: ["my comment 1", "my comment 2", "my cost 1", "my term", "my cost 2"] 变成: columnNames list: ["Comment", "Cost", "Term"] columnValues list: [["my comment 1", "my comment 2"], ["my cost 1", "my cost 2"], "my test"] 其中columnNames list中的元素Comment和Comment是重复的,要求新的List里面不能重复。 谢谢!

Java算法:N个时间段计算其中的有效时间

例如: 13:00 - 14:00 13:30 - 14:30 16:30 - 17:30 17:00 - 18:00 有效时间:3个小时! 最好有源码!

在中国程序员是青春饭吗?

今年,我也32了 ,为了不给大家误导,咨询了猎头、圈内好友,以及年过35岁的几位老程序员……舍了老脸去揭人家伤疤……希望能给大家以帮助,记得帮我点赞哦。 目录: 你以为的人生 一次又一次的伤害 猎头界的真相 如何应对互联网行业的「中年危机」 一、你以为的人生 刚入行时,拿着傲人的工资,想着好好干,以为我们的人生是这样的: 等真到了那一天,你会发现,你的人生很可能是这样的: ...

程序员请照顾好自己,周末病魔差点一套带走我。

程序员在一个周末的时间,得了重病,差点当场去世,还好及时挽救回来了。

和黑客斗争的 6 天!

互联网公司工作,很难避免不和黑客们打交道,我呆过的两家互联网公司,几乎每月每天每分钟都有黑客在公司网站上扫描。有的是寻找 Sql 注入的缺口,有的是寻找线上服务器可能存在的漏洞,大部分都...

搜狗输入法也在挑战国人的智商!

故事总是一个接着一个到来...上周写完《鲁大师已经彻底沦为一款垃圾流氓软件!》这篇文章之后,鲁大师的市场工作人员就找到了我,希望把这篇文章删除掉。经过一番沟通我先把这篇文章从公号中删除了...

总结了 150 余个神奇网站,你不来瞅瞅吗?

原博客再更新,可能就没了,之后将持续更新本篇博客。

副业收入是我做程序媛的3倍,工作外的B面人生是怎样的?

提到“程序员”,多数人脑海里首先想到的大约是:为人木讷、薪水超高、工作枯燥…… 然而,当离开工作岗位,撕去层层标签,脱下“程序员”这身外套,有的人生动又有趣,马上展现出了完全不同的A/B面人生! 不论是简单的爱好,还是正经的副业,他们都干得同样出色。偶尔,还能和程序员的特质结合,产生奇妙的“化学反应”。 @Charlotte:平日素颜示人,周末美妆博主 大家都以为程序媛也个个不修边幅,但我们也许...

MySQL数据库面试题(2020最新版)

文章目录数据库基础知识为什么要使用数据库什么是SQL?什么是MySQL?数据库三大范式是什么mysql有关权限的表都有哪几个MySQL的binlog有有几种录入格式?分别有什么区别?数据类型mysql有哪些数据类型引擎MySQL存储引擎MyISAM与InnoDB区别MyISAM索引与InnoDB索引的区别?InnoDB引擎的4大特性存储引擎选择索引什么是索引?索引有哪些优缺点?索引使用场景(重点)...

如果你是老板,你会不会踢了这样的员工?

有个好朋友ZS,是技术总监,昨天问我:“有一个老下属,跟了我很多年,做事勤勤恳恳,主动性也很好。但随着公司的发展,他的进步速度,跟不上团队的步伐了,有点...

我入职阿里后,才知道原来简历这么写

私下里,有不少读者问我:“二哥,如何才能写出一份专业的技术简历呢?我总感觉自己写的简历太烂了,所以投了无数份,都石沉大海了。”说实话,我自己好多年没有写过简历了,但我认识的一个同行,他在阿里,给我说了一些他当年写简历的方法论,我感觉太牛逼了,实在是忍不住,就分享了出来,希望能够帮助到你。 01、简历的本质 作为简历的撰写者,你必须要搞清楚一点,简历的本质是什么,它就是为了来销售你的价值主张的。往深...

优雅的替换if-else语句

场景 日常开发,if-else语句写的不少吧??当逻辑分支非常多的时候,if-else套了一层又一层,虽然业务功能倒是实现了,但是看起来是真的很不优雅,尤其是对于我这种有强迫症的程序"猿",看到这么多if-else,脑袋瓜子就嗡嗡的,总想着解锁新姿势:干掉过多的if-else!!!本文将介绍三板斧手段: 优先判断条件,条件不满足的,逻辑及时中断返回; 采用策略模式+工厂模式; 结合注解,锦...

离职半年了,老东家又发 offer,回不回?

有小伙伴问松哥这个问题,他在上海某公司,在离职了几个月后,前公司的领导联系到他,希望他能够返聘回去,他很纠结要不要回去? 俗话说好马不吃回头草,但是这个小伙伴既然感到纠结了,我觉得至少说明了两个问题:1.曾经的公司还不错;2.现在的日子也不是很如意。否则应该就不会纠结了。 老实说,松哥之前也有过类似的经历,今天就来和小伙伴们聊聊回头草到底吃不吃。 首先一个基本观点,就是离职了也没必要和老东家弄的苦...

2020阿里全球数学大赛:3万名高手、4道题、2天2夜未交卷

阿里巴巴全球数学竞赛( Alibaba Global Mathematics Competition)由马云发起,由中国科学技术协会、阿里巴巴基金会、阿里巴巴达摩院共同举办。大赛不设报名门槛,全世界爱好数学的人都可参与,不论是否出身数学专业、是否投身数学研究。 2020年阿里巴巴达摩院邀请北京大学、剑桥大学、浙江大学等高校的顶尖数学教师组建了出题组。中科院院士、美国艺术与科学院院士、北京国际数学...

男生更看重女生的身材脸蛋,还是思想?

往往,我们看不进去大段大段的逻辑。深刻的哲理,往往短而精悍,一阵见血。问:产品经理挺漂亮的,有点心动,但不知道合不合得来。男生更看重女生的身材脸蛋,还是...

程序员为什么千万不要瞎努力?

本文作者用对比非常鲜明的两个开发团队的故事,讲解了敏捷开发之道 —— 如果你的团队缺乏统一标准的环境,那么即使勤劳努力,不仅会极其耗时而且成果甚微,使用...

为什么程序员做外包会被瞧不起?

二哥,有个事想询问下您的意见,您觉得应届生值得去外包吗?公司虽然挺大的,中xx,但待遇感觉挺低,马上要报到,挺纠结的。

当HR压你价,说你只值7K,你该怎么回答?

当HR压你价,说你只值7K时,你可以流畅地回答,记住,是流畅,不能犹豫。 礼貌地说:“7K是吗?了解了。嗯~其实我对贵司的面试官印象很好。只不过,现在我的手头上已经有一份11K的offer。来面试,主要也是自己对贵司挺有兴趣的,所以过来看看……”(未完) 这段话主要是陪HR互诈的同时,从公司兴趣,公司职员印象上,都给予对方正面的肯定,既能提升HR的好感度,又能让谈判气氛融洽,为后面的发挥留足空间。...

面试:第十六章:Java中级开发(16k)

HashMap底层实现原理,红黑树,B+树,B树的结构原理 Spring的AOP和IOC是什么?它们常见的使用场景有哪些?Spring事务,事务的属性,传播行为,数据库隔离级别 Spring和SpringMVC,MyBatis以及SpringBoot的注解分别有哪些?SpringMVC的工作原理,SpringBoot框架的优点,MyBatis框架的优点 SpringCould组件有哪些,他们...

面试阿里p7,被按在地上摩擦,鬼知道我经历了什么?

面试阿里p7被问到的问题(当时我只知道第一个):@Conditional是做什么的?@Conditional多个条件是什么逻辑关系?条件判断在什么时候执...

面试了一个 31 岁程序员,让我有所触动,30岁以上的程序员该何去何从?

最近面试了一个31岁8年经验的程序猿,让我有点感慨,大龄程序猿该何去何从。

大三实习生,字节跳动面经分享,已拿Offer

说实话,自己的算法,我一个不会,太难了吧

程序员垃圾简历长什么样?

已经连续五年参加大厂校招、社招的技术面试工作,简历看的不下于万份 这篇文章会用实例告诉你,什么是差的程序员简历! 疫情快要结束了,各个公司也都开始春招了,作为即将红遍大江南北的新晋UP主,那当然要为小伙伴们做点事(手动狗头)。 就在公众号里公开征简历,义务帮大家看,并一一点评。《启舰:春招在即,义务帮大家看看简历吧》 一石激起千层浪,三天收到两百多封简历。 花光了两个星期的所有空闲时...

《Oracle Java SE编程自学与面试指南》最佳学习路线图2020年最新版(进大厂必备)

正确选择比瞎努力更重要!

《Oracle Java SE编程自学与面试指南》最佳学习路线图(2020最新版)

正确选择比瞎努力更重要!

都前后端分离了,咱就别做页面跳转了!统统 JSON 交互

文章目录1. 无状态登录1.1 什么是有状态1.2 什么是无状态1.3 如何实现无状态1.4 各自优缺点2. 登录交互2.1 前后端分离的数据交互2.2 登录成功2.3 登录失败3. 未认证处理方案4. 注销登录 这是本系列的第四篇,有小伙伴找不到之前文章,松哥给大家列一个索引出来: 挖一个大坑,Spring Security 开搞! 松哥手把手带你入门 Spring Security,别再问密...

字节跳动面试官竟然问了我JDBC?

轻松等回家通知

面试官:你连SSO都不懂,就别来面试了

大厂竟然要考我SSO,卧槽。

阿里面试官让我用Zk(Zookeeper)实现分布式锁

他可能没想到,我当场手写出来了

终于,月薪过5万了!

来看几个问题想不想月薪超过5万?想不想进入公司架构组?想不想成为项目组的负责人?想不想成为spring的高手,超越99%的对手?那么本文内容是你必须要掌握的。本文主要详解bean的生命...

自从喜欢上了B站这12个UP主,我越来越觉得自己是个废柴了!

不怕告诉你,我自从喜欢上了这12个UP主,哔哩哔哩成为了我手机上最耗电的软件,几乎每天都会看,可是吧,看的越多,我就越觉得自己是个废柴,唉,老天不公啊,不信你看看…… 间接性踌躇满志,持续性混吃等死,都是因为你们……但是,自己的学习力在慢慢变强,这是不容忽视的,推荐给你们! 都说B站是个宝,可是有人不会挖啊,没事,今天咱挖好的送你一箩筐,首先啊,我在B站上最喜欢看这个家伙的视频了,为啥 ,咱撇...

代码注释如此沙雕,会玩还是你们程序员!

某站后端代码被“开源”,同时刷遍全网的,还有代码里的那些神注释。 我们这才知道,原来程序员个个都是段子手;这么多年来,我们也走过了他们的无数套路… 首先,产品经理,是永远永远吐槽不完的!网友的评论也非常扎心,说看这些代码就像在阅读程序员的日记,每一页都写满了对产品经理的恨。 然后,也要发出直击灵魂的质问:你是尊贵的付费大会员吗? 这不禁让人想起之前某音乐app的穷逼Vip,果然,穷逼在哪里都是...

立即提问
相关内容推荐