배열에서 가능한 모든 요소 조합의 가장 작은 차이를 얻으십시오.

Question

저는 매우 긴 배열을 가지고 있으며, 2 가지 요소의 모든 가능한 조합의 최소 차이점을 가져야합니다.

이

[...] 
int diff = 1000000; // a very big difference that i'm sure is too big 
int tmpDiff; // swap 
//Compare 
for (size_t i = 0; i < N; i++) { // I try every combination of 2 elements of array 
    for (size_t j = i + 1; j < N; j++) { // don't repeat same elements 
     tmpDiff = abs(array[i] - array[j]); // get the difference 
     if (diff > tmpDiff) { // if it is smaller is the difference i need 
      diff = tmpDiff; 
     } 

    } 
} 
[...] 

그것은 너무 많은 시간이 소요 :

이

내 코드입니다. 우리는 어떻게 공연을 최적화 할 수 있습니까?

Answer 1

먼저 정렬을 정렬하십시오. 그런 다음 연속 된 값만 비교하면됩니다. 그리고 두 개의 요소 중 더 큰 것 중 어느 것이 더 큰지 알기 때문에 abs()을 사용할 필요조차 없습니다.

배열을 변경하면 안되는 경우 먼저 복사하십시오 (아래에 표시되지 않음).

qsort

#include <limits.h> 
#include <stdlib.h> 

// compare function for integer, compatible with qsort 
int int_cmp(const void *a, const void *b) 
{ 
    const int *ia = (const int *)a; // casting pointer types 
    const int *ib = (const int *)b; 
    return *ia - *ib; 
} 

... 

int diff = INT_MAX; 
int d; 

// sort 
qsort(array, N, sizeof(array[0]), int_cmp); 

// compare consecutive elements 
for (size_t i = 1; i < N; i++) { 
    d = array[i] - array[i - 1]; 
    if (d < diff) 
     diff = d; 
} 

업데이트는 퀵 알고리즘을 사용하여 배열을 정렬한다. 루프에 대해 두 개의 중첩 된 이있는 경우 정렬 비용은 O (n^2)와는 반대로 O (n ln n) 순서입니다. 더 큰 배열 (n> 100)의 경우 이것은 큰 차이를 만들 수 있습니다. 수학 만 해보세요 : 약. 500 대 10,000

qsort에 전달 된 비교 함수는 어떤 유형의 배열에서도 사용할 수 있도록 작성된 qsort과 같이 항상 까다 롭습니다. 이 함수는 배열의 두 요소에 대한 포인터를 전달합니다. 정수와 같은 작은 유형의 경우 정수를 직접 전달하면 편리 할 것입니다. 하지만 그 대신 주소를 처리해야합니다.

1. 는 정수 (int*)에 대한 포인터에 대한 유형 (void*)의 포인터에서 즉,보다 구체적인 형태로 포인터를 변환 : 그래서 당신이하는 일 두 가지입니다. 포인터 역 참조

2. , 즉이 경우 *ia 및 *ib에서 * 연산자를 사용하여 실효 값을 얻는다.

기능은 제 수가 크면 같은지 및 수가 0보다 큰 경우, 상기 제 정수 번째, 0보다 작 으면 0 미만의 수 반환 할 필요가있다. 따라서 오래된 트릭이 유용합니다. 단지 첫 번째 숫자와 두 번째 숫자의 차이를 반환하십시오.