c - 获取数组中所有可能元素组合的最小差值

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 使用Quicksort 算法对数组进行排序。如果您有两个嵌套的 for 循环，则排序的成本是 O(n ln n) 的顺序，而不是 O(n^2) 的顺序。对于更大的阵列(n > 100)，这会产生巨大的差异。算算吧:大约。 500 对 10,000。

传递给 qsort 的比较函数总是很棘手，因为 qsort 被编写成适用于任何类型的数组。该函数传递数组中两个元素(指向)的地址。对于整数这样的小类型，如果直接传递整数会很方便。但是，您必须处理地址。所以你要做两件事:

1. 将指针转换为更具体的类型，即将任何类型的指针 (void*) 转换为指向整数的指针 (int*) .

2. 取消引用指针，即使用*运算符获取有效值，在本例中为*ia和*ib .

如果第一个整数小于第二个整数，函数需要返回一个小于 0 的数字，如果它们相等则返回 0，如果第二个数字更大则返回一个大于 0 的数字。所以一个老技巧就派上用场了:只返回第一个和第二个数字之间的差值。