C 배열에서 두 번째로 큰 숫자 찾기

Question

제목에서 알 수 있듯이 배열에서 두 번째로 큰 숫자를 찾아야하며 해당 배열의 모든 숫자가 같으면 I-∞라고 써야합니다. 나는 이것을 썼다, 누군가가 내가 그것을 아마 조금 더 잘 최적화 할 수 있는지 알기 위해 점검 할 수 있었느냐? 이 배열은 내가 예를 하나

#include <stdio.h> 
int main() 
{ 
    int x[7]={90,90,78,41,21,27,35}; 
    int i, max, secmax, y; 
    secmax=0; 
    max=x[0]; 
    for(i=1;i<=7;i++) 
     { 
     if (x[i]>max) 
      { 
      secmax=max; 
      max=x[i]; 
      } 
     else if (x[i]>secmax&&x[i]<max) 
       { 
      secmax=x[i]; 
      } 
     } 

    for(i=0;i<7;i++) 
     if(x[i]==x[i+1]) 
      y++; 

    if (y==6) 
     printf("sec max to minus nieskonczonosc \n"); 
    else 
     printf("max to %d a secmax to %d\n",max,secmax); 
    return 0; 
} 

Answer 1

은 당신이 할 수있는 것입니다 :

int get_second_max(int *x, size_t n) 
{ 
    int max[2] = {-MAX_INT,-MAX_INT}; 
    int i = 0, same = 1; 
    if (NULL == x || 0 == n) 
     return -MAX_INT; 

    max[0] = x[0]; 
    max[1] = x[0]; 
    for(i = 1; i < n; i++) { 
     /* same is used to check 
     * if the array contains 
     * the same number all along. 
     */ 
     same &= (x[i] == x[i-1]); 
     /* At the i-th iteration : 
     * -> max[0] stores the maximum value 
     * -> max[1] stores the second maximum value 
     */ 

     /* We hit a new max value, we must : 
     * 1. Update the second max value with the current max value 
     * 2. Update the current max value with the new max we found 
     */ 
     if(x[i] > max[0]) { 
      max[1] = max[0]; 
      max[0] = x[i]; 
     } else if(x[i] > max[1]) { 
      max[1] = x[i]; 
     } 
    } 
    if(same) { 
     return -MAX_INT; 
    } else { 
     return max[1]; 
    } 
} 

Answer 2

당신은 전체의 마지막 스캔을 피할 수 있다고했다, 그것은 [N ... (1)] ×해야하지만이 있기 때문에 의사에게 다시 그냥 예입니다 secmax을 음의 무한대로 초기 설정합니다. 이렇게하면 항상 올바른 값을 갖게됩니다.

또한 코드에 버그가 있습니다. i<=7은 i < sizeof(x)/sizeof(x[0])으로 바꿔야합니다. 그렇지 않으면 x[i]이 세그 폴트를 줄 것입니다. 여기

Answer 3

나는 몇 가지 변경 사항이 몇 가지 의견을 추가했습니다. 코드 아래의 토론.

#include <limits.h> // for INT_MIN macro 
#include <stdio.h> 
int main() 
{ 
    // Let the compiler count length of array. 
    // -- declare "x[]", no need to specify length 
    const int x[] = { 90, 90, 78, 41, 21, 27, 35 }; 
    // -- use sizeof() math to find length of array 
    // -- use const int rather than #define so debugger can see value 
    const int len = sizeof(x)/sizeof(x[0]); 
    int i, max, secmax, same_count; 

    if (0 == len) 
    { 
     // zero-length list: return INT_MIN 
     printf("sec max to minus nieskonczonosc: %d\n", INT_MIN); 
     return 0; 
    } 

    secmax = max = INT_MIN; 

    same_count = 0; 

    // start loop at 0 
    for(i = 0; i < len; ++i) 
     { 
     // We'll use the same idea you originally used to find if all values were 
     // the same, but do it as part of the same loop. No need to loop over 
     // the values twice. For a short list, looping twice is not a big deal, 
     // but for really large data sets it will save lots of time to do it this way. 
     same_count += (x[0] == x[i]); 

     if (x[i]>max) 
      { 
      // Found value greater than current max; shift max down to secmax 
      // and save new max value. 
      secmax=max; 
      max=x[i]; 
      } 
     else if (x[i]>secmax && x[i]<max) 
      { 
      // It wasn't greater than max, but is greater than secmax. 
      // Save new secmax value. 
      secmax=x[i]; 
      } 
     } 

    if (len == same_count) 
     printf("sec max to minus nieskonczonosc: %d\n", INT_MIN); 
    else 
     printf("max to %d a secmax to %d\n",max,secmax); 

    return 0; 
} 

실행 시간을 향상시키기 위해 할 수있는 일은 많지 않습니다. 코드는 이미 원하는 값을 찾기 위해 직접적으로 작업을 수행하고 있습니다.

우리가 할 수있는 한 가지는 첫 번째 루프에서 작업을 수행하여 두 번째 루프를 제거하는 것입니다.

@ Rerito의 대답은 알고리즘을 변경했습니다. 동일한 값의 개수를 계산하는 대신, 그 값이 1 비트로 시작되고 값 비교와 함께 비트 별 "and"가 사용됩니다. 비교가 실패하면 비교 결과는 0이되고 값 0 인 비트 "and"는 0이됩니다. 따라서 비교가 실패하면 초기 1 비트는 0 비트로 지워지고 루프가 끝났습니다. 1 비트가 여전히 설정되어 있으면 모든 값이 동일해야합니다.

나는 얼마나 많은 값이 같은지를 세는 기본 알고리즘을 유지하고 그 수와 길이가 일치하는지 확인했다. y이라는 이름이 정보가 없기 때문에 카운팅 변수의 이름을 변경 했으므로 카운트를 첫 번째 루프 내부로 이동 한 다음 (두 번째 루프를 제거함) 배열 값을 변경할 수 있도록 코드를 수정했습니다. 그냥 일이야.

연결되지 않은 "마법"값을 코드에 뿌리는 것은 나쁜 습관입니다. 원래 코드는 세 곳에서 7이고 6 ... 따라서 누군가가 배열의 길이를 변경하면 버그가 발생합니다. 내 코드는 C 컴파일러에서 배열에있는 값의 수를 계산하고 상수 (len)를 설정 한 다음 해당 상수를 독점적으로 사용합니다. 따라서 단순히 배열에 값을 추가하거나 제거 할 수 있으며 변경된 코드는 여전히 올바르게 작동합니다.

EDIT : @sds는 다음과 같이 썼습니다. "secmax를 처음으로 음의 무한대로 설정하면 전체 배열의 마지막 스캔을 피할 수 있습니다. 이렇게하면 항상 올바른 값을 갖게됩니다."

아, 맞아! 코드가 max보다 작은 값을 볼 때 코드가 secmax으로 만 설정되고 모든 값이 동일한 경우에만 코드가 작성되므로 모든 값이 동일하면 반환 할 값으로 secmax을 설정해야합니다. , secmax은 절대로 변경되지 않습니다.