今天做编程题的时候遇到了一道题,地址如下:
https://www.nowcoder.com/questionTerminal/14a045880df44cf79626f079bd9f07f1?f=discussion
题目叫做:ん...红茶?
题目大概意思就是给定一个数c,然后让你从数组中找出所有满足a+b=c的ab值并输出。
小弟我白菜一颗,又白又菜,一开始没啥头绪,后来 抄袭 学习别的大佬提交的代码,写出了自己的答案,代码如下:
import java.util.*; public class Main { public static void main(String[] args) { Scanner input =new Scanner(System.in); int n=input.nextInt(); int []cups= new int[n]; for(int i=0;i<cups.length;i++) { cups[i]=input.nextInt(); } int W=input.nextInt(); Arrays.sort(cups); int end=cups.length-1; for(int i=0;i<end;) { if(cups[i]+cups[end]==W) { System.out.println(cups[i++]+" "+cups[end]); n=-1; continue; } if(cups[i]+cups[end]>W) { end--; continue; } if(cups[i]+cups[end]<W) { i++; continue; } } if(n!=-1) { System.out.println("NO"); } input.close(); } }
提交运行没问题(这里一开始有个问题,即当满足条件输出后,我把i和end分别+1和-1,这时候只能通过95%,我不太理解为啥,还希望有大佬能慷慨解答下。)但是效率非常低,如下:
虽然答案是正确了,但是和第一名的大佬相比,足足慢了一倍还多!
(这个地方,贴出名字应该没有问题吧,如果有问题还请告知小弟,立马就改(303的单位是毫秒))
对比了一下我和大佬的代码,只有一处不同,我用了util包里的Scanner,而大佬用的是io包中的BufferedReader
本着不会就照猫画虎微创新的理念,我修改了下我的代码,如下:
import java.io.*; import java.util.*; public class Main { public static void main(String[] args)throws IOException { BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(input.readLine()); String[] cs=input.readLine().split(" "); int []cups= new int[n]; for(int i=0;i<n;i++) { cups[i]=Integer.parseInt(cs[i]); } int W=Integer.parseInt(input.readLine()); Arrays.sort(cups); int end=cups.length-1; for(int i=0;i<end;) { if(cups[i]+cups[end]==W) { System.out.println(cups[i++]+" "+cups[end]); n=-1; continue; } if(cups[i]+cups[end]>W) { end--; continue; } if(cups[i]+cups[end]<W) { i++; continue; } } if(n!=-1) { System.out.println("NO"); } } }
改用BufferedReader之后的代码结果:
(同上,单位还是毫秒)
可以看到,运行时间只用了原来的一半,而占用空间也只有原来的1/3,虽然比不上大佬的代码快,但是也已经比原来好很多了,而且更改的地方也只有输入的地方从Scanner变成了BufferedReader,所以我想我们可以认为这些时间和空间上的优势都是由BufferedReader带来的。
光听人说BufferedReader比Scanner快,竟然能快这么多!(像不像广告)
为什么这么快呢?因为Scanner是要对输入数据进行正则解析的,而BufferedReader则只是简单的进行读入操作,所以说要快。
但是我写了一点又突然想起,我在用Scanner和BufferedReader的时候,输入方式并不同,Scanner是直接用nextInt()来输入,而BufferedReader是用readLine()读入一个字符串然后用split()方法把它以空格来分开,最后再用Integer的parseInt()方法把字符串数组里的每一个数字都转换成数字存入一个整形数组里。为了避免是因为nextInt()方法拖慢时间,于是乎我又去改了改代码:
import java.util.*; public class Main { public static void main(String[] args) { Scanner input =new Scanner(System.in); int n=input.nextInt(); input.nextLine(); String css=input.nextLine(); String []cs = css.split(" "); int []cups=new int[cs.length]; for(int i=0;i<cups.length;i++) { cups[i]=Integer.parseInt(cs[i]); } int W=input.nextInt(); Arrays.sort(cups); int end=cups.length-1; for(int i=0;i<end;) { if(cups[i]+cups[end]==W) { System.out.println(cups[i++]+" "+cups[end]); n=-1; continue; } if(cups[i]+cups[end]>W) { end--; continue; } if(cups[i]+cups[end]<W) { i++; continue; } } if(n!=-1) { System.out.println("NO"); } input.close(); } }
运行结果:
可以看到,更改了输入逻辑之后,代码相较于之前的输入逻辑快了大概300多ms,但是跟BufferedReader比起来还是差了大概100ms.
究其原因的话,我认为:
在第一段代码中,直接使用nextInt方法进行赋值,相当于用了n次的Scanner,而第三种只调用了3次,所以会快很多,但是比起BufferedReader来说就慢一点了,大概也在个1/2到1/3左右,这种编程题里面自然并不关键,只要能AC了,怎么着都行,但是在开发大型软件的时候,这种差距可能就比较大了(虽然我并没有开发经验,但我还是要瞎BB一下,如果有啥不对的还请大家指出,让小弟我学习学习)