獲取陣列

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()，因爲你知道這兩個元素中的哪一個更大。

如果陣列不能被改變，第一複製（未如下所示）。

#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; 
} 

更新

qsort排序使用快速排序算法的數組。如果對於循環有兩個嵌套的，則排序的成本爲O（n ln n），而不是O（n^2）。對於更大的陣列（n> 100），這可以產生巨大的差異。只要做數學：約。 500與10,000。

傳遞給qsort的比較函數總是很棘手，因爲qsort被編寫爲可以與任何類型的數組一起工作。該函數傳遞（指向）數組中兩個元素的地址。對於像integer這樣的小類型，如果它直接傳遞了整數，它會很方便。但是，你必須處理地址。所以你要做的就是兩件事情：

1. 轉換的指針更具體的類型，即從任何類型（void*）爲指針的指針整數（int*）。

2. 解除引用指針，即，通過使用操作員*，在這種情況下*ia和*ib得到有效值。

的功能需要返回大於0的數少，如果的第一個整數比第二一種，0較小，如果它們是相等的和大於0的數，如果所述第二數量較大。因此，一個古老的技巧派上用場：只需返回第一個和第二個數字之間的差異。