c# - 在数组中，我们如何找到 2 个元素在给定数字中的差异..？少于 O(n^2) 时间

Question

<分区>

Answer 1

原始答案 - O(n log n)

怎么样:

• 对数组(或副本)进行排序。这是 O(n log n)
• 遍历数组，对每个值 x 进行二分查找 x + no
  • 每次二分查找都是O(log n)
  • 总体 O(n log n)

总成本:O(n log n)

---

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

FWIW, you don't have to do a binary search for x + no. As you iterate over the array, you can maintain a second iteration point in advance of the first one. Since the array is sorted, at each step x + no is greater than or equal to what x + no was in the previous step, so a linear search starting at the second iteration point from the previous step only ever goes forward and hence is O(n) total for the whole outer iteration, even though it isn't O(1) for each of the n steps.

这仍然需要事先进行排序，不过这是 O(n log n)。

---

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
    }
}