3

我们得到了一个整数数组：

45, 10, 56, 42, 95, 78.

我们必须找到差异最小的两个元素。我以线性时间复杂度做到了这一点，但它只适用于完全领先于二次复杂度的运行时间的排序顺序。我们有什么方法可以以对数或线性时间复杂度进行计算吗？

提前致谢。

4

2 回答 2

1

只需使用始终位于的 Heapsort 对数组进行排序O( n * log n)。之后，您应用您的算法，正如您所说，在O(n). 所以你将拥有n + n * log n仍在O(n * log n)

于 2015-08-02T15:37:55.910 回答
-1

`bool checkPair(int A[], int n, int K) { 取大小为 O(n) 的哈希表 H for (i = 0 to n-1)

  { 
  int x = K - A[i]
  if (H.search(x) is true) 
      return 1
  H.insert(A[i])

} 返回 -1 } `

于 2021-07-21T21:24:18.787 回答