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

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 被编写成可以与任何类型的数组一起使用。该函数传递数组中两个元素（指向）的地址。对于整数这样的小类型，如果直接传递整数会很方便。但是，您必须处理地址。所以你要做两件事：

将指针转换为更具体的类型，即从任何类型的指针 (void*) 到指向整数 (int*) 的指针。
取消引用指针，即使用*运算符获取有效值，在本例中为*ia和*ib.

函数需要 return 如果第一个整数小于第二个整数则小于 0 的数字，如果它们相等则为 0，如果第二个数字更大则为大于 0 的数字。所以一个老把戏派上用场了：只是 return 第一个和第二个数字之间的差异。

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

Get the smallest difference of all possible element combinations in an array

c

arrays

sorting

optimization

difference