algorithm - 使用蛮力计算两个不同数组元素之间的最小绝对值差

Question

• 输入：实数数组 a[1..n]；
• 输出：两个不同数组元素之间的最小绝对值差。

我想要一个同样的蛮力算法。

任何人有任何想法？

Answer 1

如果元素已排序，那么您可能只需要按顺序比较每对项目： [1, 3, 6, 7, 28] -> 7-6 给出最小距离

为了强行使用它，我想您可以从每个值中减去每个值（n * n-1）并跟踪哪个对最小。您需要确保不要从自身中减去相同的元素，但具有相同值的元素应该允许作为对。

Answer 2

如果你想暴力破解它，只需遍历每一对元素：

min = infinity

for i=1 to n-1
    for j = i+1 to n
        if abs(a[i]-a[j]) < min
            min = abs(a[i]-a[j])

这需要O(n^2)时间。您可以O(n log n)通过首先对列表进行排序来获得时间：

sort(a)
min = infinity

for i = 1 to n-1
    if abs(a[i+1]-a[i]) < min
        min = abs(a[i+1]-a[i])