如何找到数组中的最小距离？

Question

输入是排序整数数组，我必须找到数字 |a.[i] - a.[j]| 之间的最小距离和给定的数字 d。如何找到最小距离？

distance = ||a.[i]-a.[j]| - d|

Answer 1

这看起来很容易在线性时间内完成。鉴于一些评论中普遍存在的困惑，我可能遗漏了一些使我的解决方案无用的东西。无论如何，我开始了：

I know this looks much like Java, however it's intended to be pseudocode.

Array is a, array size is n, array elements are a[0] to a[n-1]
Target distance is d, assumed non-negative

i=0;
j=0;
solutionI = 0;
solutionJ = 0;
minError = d;

while (j < n)
{
  error = abs(a[j]-a[i]-d)  // abs is absolute value
  if (error < minError)
  {
    solutionI = i;
    solutionJ = j;
    minError = error;
  }

  if (a[j] - a[i] <= d)
  {
    // Gap between a[i] and a[j] is too short, increase j to increase gap
    // Note we also advance j when we have an exact match
    // This is to keep always j>=i even when d=0
    j++;
  }
  else
  {
    // Gap between a[i] and a[j] is too long, increase i to decrease gap
    i++;
  }
}

Now solutionI and solutionJ mark the closest match to gap d
Also, minError tells how far we are from target distance d

如何找到数组中的最小距离？

How to find a minimal distance in array?

sorting

algorithm

distance