首先感谢面试官,看了我的博客,并认真读了我的博客,并针对求第三大数的算法,给出了我宝贵的建议;
对于我来说,这样才有有意,这样学习才能成长,这样进步才能更快;
首先题目很简单,就是求若干个数中第三个数是多少?我第一次写的程序如下:
package test; /** * @title 求一个数组中第三大数是多少 * @author 郑云飞 * @date 2014-04-13 * */ public class ArrayDemo{ public static void main(String[] args){ int arr[]={1,3,5,7,23,122,2344}; int x=show(arr); System.out.println("第三大数="+x); } /** * @author 郑云飞 * @date 2014-04-13 * @param arr 数组 * @return 第三大数 */ public static int show(int arr[]){ for(int i=0;i<arr.length-1;i++){ for(int j=i+1;j<arr.length;j++){ if(arr[i]>arr[j]){ temp(arr,i,j);//交换位置 } } } return arr[arr.length-3]; } /** * @title 交换位置 * @param arr 数组名 * @param a 参数a * @param b 参数b */ public static void temp(int arr[],int a,int b){ int t=arr[a]; arr[a]=arr[b]; arr[b]=t; } }
面试官看过之后说:我的代码是先排序再找出第三大数,效率不是很高,让我继续琢磨一下,并给了我温馨提示:说并不需要全体排序就能找出来。
看过短信之后,我首先回忆了一下,当初在凤凰汇咖啡厅的时候,面试官曾经给了我暗示。我按照他当初给我的提示,反复思考着,最后想到了用冒泡排序实现升序的过程,只执行三次排查即可,第三大的数会排到倒数第3位的位置,改进后的代码如下:
package com.yting.hadoop.rpc; /** * @title 求一个数组中第三大数是多少 * @author 郑云飞 * @date 2014-04-16 * */ public class ArrayDemo { public static void main(String[] args) { int a[]={10,9,8,7,6,5,4,3,2,1};//随便定义一个数组,并初始化 int i,j; //用冒泡排序实现升序的过程,只执行三次排查即可,第三大的数会排到倒数第3位的位置 for(i=0;i<3;i++) { for(j=0;j<10-i-1;j++) { if(a[j]>a[j+1]) { temp(a,j,j+1); } } } System.out.print("最三大数:"+a[7]); } /** * 交换位置 * @author zhengYunfei * @date 2014-04-16 * @param arr 数组名 * @param a 参数a * @param b 参数b */ public static void temp(int arr[],int a,int b){ int t=arr[a]; arr[a]=arr[b]; arr[b]=t; } }
下面就来算算这2个程序运行时间,看看到底哪个效率更高
首先我们定义一个10000个数的一位数组
int a[] = new int[10000]; for(int i=0;i<10000;i++){ a[i]=i; }
用第一个程序:
package com.yting.hadoop.rpc; /** * @title 求一个数组中第三大数是多少 * @author 郑云飞 * @date 2014-04-13 * */ public class ArrayDemo2{ public static void main(String[] args){ long pre=System.currentTimeMillis(); int arr[] = new int[10000]; for(int i=0;i<10000;i++){ arr[i]=i; } int x=show(arr); long last=System.currentTimeMillis(); long time=last-pre; System.out.println("第三大数="+x+"\t"+"耗时:"+time+"毫秒"); } /** * @author 郑云飞 * @date 2014-04-13 * @param arr 数组 * @return 第三大数 */ public static int show(int arr[]){ for(int i=0;i<arr.length-1;i++){ for(int j=i+1;j<arr.length;j++){ if(arr[i]>arr[j]){ temp(arr,i,j);//交换位置 } } } return arr[arr.length-3]; } /** * @title 交换位置 * @param arr 数组名 * @param a 参数a * @param b 参数b */ public static void temp(int arr[],int a,int b){ int t=arr[a]; arr[a]=arr[b]; arr[b]=t; } }
运行结果如下:
第三大数=9997 耗时:85毫秒
改进后的程序:
package com.yting.hadoop.rpc; /** * @title 求一个数组中第三大数是多少 * @author 郑云飞 * @date 2014-04-16 * */ public class ArrayDemo { public static void main(String[] args) { long pre=System.currentTimeMillis(); int a[] = new int[10000]; for(int i=0;i<10000;i++){ a[i]=i; } int i,j; //用冒泡排序实现升序的过程,只执行三次排查即可,第三大的数会排到倒数第3位的位置 for(i=0;i<3;i++) { for(j=0;j<10000-i-1;j++) { if(a[j]>a[j+1]) { temp(a,j,j+1); } } } long last=System.currentTimeMillis(); long time=last-pre; System.out.println("10000个数中第三大数是"+a[10000-3]+"\t耗时:"+time+"毫秒"); } /** * 交换位置 * @author zhengYunfei * @date 2014-04-16 * @param arr 数组名 * @param a 参数a * @param b 参数b */ public static void temp(int arr[],int a,int b){ int t=arr[a]; arr[a]=arr[b]; arr[b]=t; } }
运行结果如下:
10000个数中第三大数是9997 耗时:1毫秒
再将数组提升到100000个,前者耗时:
第三大数=99997 耗时:13906毫秒
改进后的程序耗时:
100000个数中第三大数是99997 耗时:7毫秒
数组个数越大,2者的差别越明显。
所以执行同样的结果,不同的算法,执行的效率相差真的很大,所以,编程当中优化算法,优化执行效率,才是编程之美。
再次感谢面试官,让我对这个程序进行了更深层次的研究。还希望请您再阅读一下,看看有没有更好的更有效率的算法,尽情期待。
优化后的算法,请看紧跟此博客其后的下一篇博客:深入探究第3大数
相关推荐
21届的福建电信面试流程
中国电信笔试面试资料集合,包含各种资料(IT类的)
历年来各个地区的中国电信笔试面试资料下载
2013年最新版中国电信测试面试题题库,内容全面广泛深刻
【中国电信】面试经验分享.docx
里面有大量的中国电信笔试面试题目,通信行业的其他公司,也可作参考用,希望能为找工作的同学提供一点帮助
中国电信财务管理岗笔试题及面试题 中国电信财务管理岗笔试题及面试题 中国电信财务管理岗笔试题及面试题
电信面试技巧,细节以及流程,以及过来人的经验
中国电信交换专业基础知识,可以参考一下,希望能提供帮助
有兴趣加入运营商中国电信或需要笔试、面试的毕业生,可以免费下载相关复习资料。祝大家可以顺利通过笔试和面试。
电信笔试面试必须要知道的东西,对你去电信肯定有帮助!
(1912制作)中国电信求职笔试题面试题集总(总34页) 1912 中国电信 笔试题 面试题
电信笔试的几道题,是我在复习的时候一位电信的朋友送我的,希望对大家有用
上个星期,去深圳一家搞ARM开发的公司面试,HR叫我做了一份卷子,里面都是C编程,心中暗喜,因为这些题基本上都在程序员面试宝典里见过。后来回到学校,在网上搜索,原来这些题都是嵌入式工程师的经典面试题目,很多...
中国电信2016年IT研发工程师笔试题及答案.pdf
包括了很多IT公司的面试题,笔试题(公司很多,都已经不知道有多少公司了)(举例如:华为,中兴,摩托罗拉,移动,电信等等等等~~~) 包括了硬件知识题库,软件知识题库,射频知识题库,智力题等叉叉叉叉题库,我都...
牛客网——互联网学习求职必备神器 名企校招历年笔试面试真题, 尽在牛客网 牛客网, 互联网人都在用的学习求职神器 ②JSP 语法, EL, 内置对象 ③Listener 和 filter 2、 Web 编程进阶 ①Servlet、 标签的作用 ②...
中国电信总部招聘礼包 内容包括:笔试 面试 职业心得体会