| ||||||||||
| 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