Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:java改了好多次,终于不超时了

Posted by tears743 at 2015-03-30 20:29:39 on Problem 1002
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator