인쇄

Question

최근에 나는이

같은 문제를 통과 한 순서대로 최대 횟수를 표시 수는 N 정수의 시퀀스를 읽고 수를 인쇄하는 프로그램을 작성 시간 순서대로. 제약 1 < = N < = 10000 정수는 I가 다음 코드를 writen있다 [-100,100]

범위에있을 것이다 :

main() 
{int arr[201],max=0,maxelement,n,i,num; 
int t; 
scanf("%d",&n); 
int *storenum=(int *)malloc(sizeof(int)*n); 
for(i=0;i<201;i++) 
{ 
      arr[i]=0; 
} 
for(i=0;i<n;i++) 
{ 
      scanf("%d",&num); 
      storenum[i]=num; 
      if(num<=100 && num>=-100) 
      { 
         arr[num+100]=arr[num+100]+1; 

      } 
} 
for(i=0;i<n;i++) 
{ 
      int t=storenum[i]+100; 


     if(arr[t]>max) 
     { maxelement=storenum[i]; 
     max=arr[t];} 

} 

    printf("\n\n%d",maxelement);  

getch(); 
} 

이제 I이 코드를 최적화되지 생각한다. .. 시간과 공간의 복잡성을 줄이고 솔루션을 개선 할 수있는 솔루션을 원합니다.

Answer 1

코드가 최적의 상태에 매우 가깝게 보입니다. 귀하의 제약 조건을 고려할 때 조금 더 나아질 수 있습니다.

1. memset을 사용할 때 memset을 사용하십시오. 그렇습니다. 컴파일러는 99 %의 시간을 집어들 것입니다. 그러나 왜 귀찮게합니까?

   for(i=0;i<201;i++) arr[i]=0; // becomes 
   memset(arr, '\0', sizeof(arr)) 
   

2. 특정 항목의 수는 그것이 USHORT 유지 될 수있다 즉, 10000보다 클 수 있습니다!

   int arr[201]; // becomes 
   uint16_t arr[201]; 
   

3. 두 번째 루프 대신 for(i = -100; i <= 100; i++)에서 이동하고 arr 이상 단지 루프한다.

4. 코드가 엉뚱한 것입니다. 일관된 들여 쓰기, 중괄호 스타일을 사용하고 동일한 줄에 50 개의 선언을 밀어 넣지 마십시오. 요소 사이에는 공백이 있습니다. arr은 아마도 뭔가 의미있는 이름을 붙여야하는데, 나는 counts을 좋아합니다. Gnu 스타일 C를 사용하려고하는 것처럼 보이지만 K & R도 작동합니다. 실제로 스타일 가이드를 선택하고 살펴 봅니다.

Answer 2

N 개의 항목을 모두 반복하지 않아도 최대 201 개의 항목을 반복하면됩니다.