arrays - 火车站到中心的距离等于 N 英里

Question

我有一个非常非常大的正整数数组，代表某个火车站离中心有多远，例如:

  S = {10, 200, 1000, 1500, 2019, 2200}

S[0] 火车站距市中心 10 英里。 S 总是按升序排序，在任何时间点，也在算法开始之前。只是简单地总是。

我想找到一个函数来检查是否存在两个距离恰好为 N 英里的火车站。

例如: N = 1300 会给我真实的结果，因为 1500 - 200 = 1300。

第一种方法

迭代 S 并检查每个元素到另一个元素的距离是否为 N。这给了我两个循环，我猜 O(n^2)。我不想要 O(n^2)，因为数组可能非常大，需要更好的性能。

其他方法

我做了很多研究，但我发现 O(n) 是可能的。我想要这个时间复杂度。我的解决方案看起来像这样，但不幸的是它根本无法解决。

  int a[] = {10, 200, 1000, 1500, 2019, 2200};
  int size = 6;
  int left = 0;
  int right = size - 1;
  int x, y, distance, tempdis;
  int N = 1300;

  while(left < right)
  {
    x = a[left];
    y = a[right];
    tempdis = x - y;
    distance = tempdis < 0 ? tempdis*(-1) : tempdis;

    if(distance == N)
    {
       printf("found pair: %d %d\n", left, right);
       break;
    }
    if(distance > N)
      left++;

    if(distance < N)
      right--;
  }

Answer 1

您可以通过仅递增两个指针 O(n) 来实现线性时间 ( i)和 j .你想找i和 j这样 a[j] - a[i] == N .逻辑很简单:

• 如果a[j] - a[i] < N : 增加 j (距离变大)
• 如果a[j] - a[i] > N : 增加 i (距离变小)

就是这样!在代码中:

int i = 0;
int j = 0;

while ((a[j] - a[i] != N) && j < size) { // size is length of a
    if (a[j] - a[i] < N) {
        j++;
    } else {
        i++;
    }
}

if (j < size) {
    printf("found pair: %d %d\n", i, j);
}

---

正确性的手动证明:原则上，我们应该检查每个 a[j]反对所有a[i]这可能会提供解决方案。也就是说，对于每个 j ，我们检查一个范围 p_j <= i <= q_j , 这样 a[j] - a[p_j] > N和 a[j] - a[q_j] < N .如果有涉及j的解决方案, 它必须在 i 的范围内找到值(value)观。

现在，这个算法几乎做到了，有一个异常(exception):有时我们增加 j连续多次，所以我们显然没有针对整个范围进行检查。我们递增 j再次，因为 a[j] - a[i] < N .然而，如果发生这种情况，我们也知道 a[j] - a[i-1] > N .我留给你来验证这一点。

这意味着我们检查j针对所有 i 的范围可能提供解决方案的值。因此结果是正确的。

我们有两个指针。在每一步中，一个指针都会递增。 2 ( j ) 中较大者的大小以 n 为界，所以这在 O(n) 中运行时间。