Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:java改了好多次,终于不超时了In Reply To:Re:java改了好多次,终于不超时了 Posted by:tears743 at 2015-03-30 19:59:27 > 我也用的JAVA ,还是超时。。。我都无语了。。。自己写排序,统计。。。各种都超时。。现在用的是treeset还是超时。。。 > 看看代码,怎么改啊,,,木有方向了 > > public static void main(String[] args) { > long a=System.currentTimeMillis(); > Scanner input = new Scanner(System.in); > ArrayList<String> dlist = new ArrayList<String>(); > TreeSet<String> dlist1 =new TreeSet<String>() ; > ArrayList<Integer> clist = new ArrayList<Integer>(); > TreeSet<Integer> clist1 = new TreeSet<Integer>(); > String number; > int count= 0; > count = input.nextInt(); > for(int i=0;i<=count;i++){ > > number =input.nextLine(); > number=number.replace("-",""); > number=number.replace("Q",""); > number=number.replace("Z",""); > number = number.replaceAll("[A-C]", "2"); > number = number.replaceAll("[D-F]", "3"); > number = number.replaceAll("[G-I]", "4"); > number = number.replaceAll("[J-L]", "5"); > number = number.replaceAll("[M-O]", "6"); > number = number.replaceAll("[P]|[R-S]", "7"); > number = number.replaceAll("[T-V]", "8"); > number = number.replaceAll("[W-Y]", "9"); > dlist.add(number); > dlist1.add(number); > } > long b=System.currentTimeMillis(); > Iterator<String> iter=dlist1.iterator(); > Boolean f=false; > int c = 0; > while(iter.hasNext()){ > StringBuffer sb = new StringBuffer(iter.next()); > c = Collections.frequency(dlist,sb.toString()); > if(c>1){ > System.out.println(sb.insert(3, "-")+" "+c); > f=true; > } > } > if(!f){ > System.out.println("No duplicates."); > } > // System.out.println("\r<br>执行耗时 : "+(b-a)+" ms "); > // System.out.println("\r<br>执行耗时 : "+(System.currentTimeMillis()-b)+" ms "); > > > } > > } 额,估计是 c = Collections.frequency(dlist,sb.toString());这句,最坏情况100000数据无重复情况下时间复杂度是n2,难怪会慢。。。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator