获取阵列

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的数，如果所述第二数量较大。因此，一个古老的技巧派上用场：只需返回第一个和第二个数字之间的差异。