在bash中查找排序数组中数字之间的最小差值。

Question

我正在做一个代码挑战，在给定的数字下，我必须找到最小的差异。例如：

[3,5,8,9]

Result : 1 (9-8)

问题是，实现这个难题的最终测试使用了大量的数字，而我的代码没有得到足够的优化。

在查找minimu差异之前，我对数组进行如下排序：

IFS=$'\n' sorted=($(sort -n <<<"${array[*]}"))

然后，我对数组做了一个for循环，以找到最小的，但这需要太多的时间，所以我尝试执行i+4而不是i++，但我不认为这是真正的问题。

下面是我寻找最小的代码：

smallest=5000
for (( i=2; i<N; i=$((i+1)) ));do
    diff=$((${sorted[i]}-${sorted[i-1]}))
    if [ $diff -lt $smallest ]; then
        smallest=$diff
    fi
done

你知不知道我能做些什么，才能有足够的优化来通过测试？顺便说一下，我对Bash几乎一无所知，我用python编写代码。

Answer 1

我怀疑这会有帮助；shell根本不适合于快速的数值计算。唯一的区别是，我将数组索引操作的数量减少了一半。

# No need to guess at an upper bound
N=${#sorted[@]}
smallest=$((${sorted[N-1]} - ${sorted[0]}))

current=${sorted[0]}
for next in "${sorted[@]:1}"; do
    diff=$(($next - $current))
    if [ $diff -lt $smallest ]; then
        smallest=$diff
    fi
    current=$next
done

我不认为使用C样式的循环比迭代数组的元素更快，但如果是这样，下面是如何处理：

# Indices run from 0 to N-1
# No need for $((...)); ((...)) is already an arithmetic context
current=${sorted[0]}
for ((i=1; i<N; i++)); do
    next=${sorted[i]}
    diff=$(($next - $current))
    if [ $diff -lt $smallest ]; then
        smallest=$diff
    fi
    current=$next
done

最后，您可以尝试完全不使用数组，而只是从标准输入中读取数据。

sort -n <<EOF |
5
3
9
8
EOF
| {
    smallest=5000   # Now you do have to guess again
    read current
    while read next; do
        diff=$((next - current))
        if [ $diff -lt $smallest ]; then
            smallest=$diff
        fi
        current=$next
    done
}