在数组中，我们如何找到2个元素'；s在给定数字中的差异.?小于O(n^2)时间

本文关键字：小于 时间 数字 何找 我们 数组 2个 元素 | 更新日期: 2023-09-27 18:11:53

可能重复：
检查2个阵列的数量加起来是否为I

我的问题是，我假设有一个给定的数字no=10;和一个数组A，我必须找到那些不，谁的区别就是给定的不。。例如：-A[5]-A[3]=10;然后打印print(A[5]); Print(A[5])
我有一个算法可以在O(n^2)时间内完成，但我们需要更好的
我的直觉可能是在短阵之后做点什么。。。。。但是怎么。。因为短路后，它还需要两个回路来检查这种情况
我有点困惑。。。。。。

在数组中，我们如何找到2个元素'；s在给定数字中的差异.?小于O(n^2)时间

原始答案-O(n log n(

怎么样：

  • 对数组(或副本(进行排序。这是O(n log n(
  • 在数组上迭代，并对每个值x执行x + no的二进制搜索
    • 每个二进制搜索都是O(logn(
    • 总体O(n log n(

总成本：O(n log n(

根据Steve Jessop的评论，对上述内容进行修改：

FWIW，您不必对x+no进行二进制搜索。当您对数组进行迭代时，您可以在第一个迭代点之前维护第二个迭代点。由于数组是排序的，在每一步，x+no都大于或等于前一步中的x+no，因此从前一步的第二个迭代点开始的线性搜索只向前进行，因此对于整个外部迭代来说是O(n(总和，即使对于n个步骤中的每一个来说都不是O(1(。

这仍然需要预先进行排序，即O(n-logn(。

最佳答案IMO(易于实现和O(n((

编辑：或者，当然，构建一个HashSet，使包含性检查更快(假设创建集合分摊为O(n(，查找为O(1((：

HashSet<int> values = new HashSet<int>(array);
foreach (int value in array)
{
    if (values.Contains(value + no))
    {
        // Found a match
    }
}
相关文章：