중첩 된 "for"루프를 Java

Question

에서 피할 수있는 방법은 없으므로 코딩 문제를 해결하고 타임 아웃으로 인해 많은 수의 입력이있는 테스트 케이스에서 코드가 실패했습니다.

"카운트"시간의 시뮬레이션을 수행해야합니다. 각 시뮬레이션은 "크기"시간 0에서 364 사이의 임의의 숫자를 생성합니다. 두 숫자가 동일한 인덱스에 저장되어 있으면 숫자가 저장되고 카운트되어야합니다 (즉, 카운트가 '2'일 때). ++ 히트 비율 "카운트"와 관련하여

public double calculate(int size, int count) { 
     // TODO -- add your code here 
     int Hits=0; 
     for(int j=1;j<=count;j++) {  // number of simulation 

      int BirthDays[]=new int[365]; 
      Random rnd = new Random(); 
      rnd.setSeed(j); 

      for(int i=0;i<size;i++){  //number of people 
       int x=rnd.nextInt(365); 
       BirthDays[x]=BirthDays[x]+1; 
       if(BirthDays[x]>=2){ 
        Hits++; 
        break; 
       } 
      } 

     } 
     return(((float)Hits/count)*100); 

    } 

그렇다면 시간 복잡성을 줄일 수있는 방법이 있습니까? 데이터 구조를 변경할 수 있습니다 배열에 독점되지 않습니다.

Answer 1

내가 즉시 볼 수있는 가장 큰 시간 절약은 Random rnd = new Random()을 루프 밖으로 이동시키는 것입니다. 매번 새 인스턴스를 만들 필요가 없으며 상당히 느립니다.

public double calculate(int size, int count) {  
    int max = 365; 
    int birthDays[] = new int[max]; 
    Random rnd = new Random(); 
    int hits = 0; 
    for(int j = 1; j <= count; j++) { 
     Arrays.fill(birthDays, 0); 
     rnd.setSeed(j); 
     for(int i = 0; i < size; i++) { 
      int x = rnd.nextInt(max); 
      birthDays[x]++; 
      if(birthDays[x] >=2) { 
       hits++; 
       break; 
      } 
     } 

    } 
    return (hits/count) * 100; 

}