这是一道面试题。给定一个排序的整数数组和数字 z，找到数组中的所有对 (x, y)，使得 x + y < z。能比 O(n^2) 做得更好吗？
PS 我知道我们可以在 O(N) 中找到所有对 (x, y | x + y == z)。
问问题
1602 次
7 回答
9
您不一定能在 O(n) 时间内找到所有此类对，因为可能存在 O(n 2 ) 对具有此属性的值。一般来说，一个算法的运行时间不能少于它产生的值的数量。
希望这可以帮助！
于 2012-09-02T07:05:55.253 回答
5
在生成中，不，它不能。考虑在数组中x + y < z对于 allx的情况。y您必须触摸（例如显示）n(n - 1)/2集合中所有可能的配对。这基本上是 O(n^2)。
于 2012-09-02T07:06:24.097 回答
2
如果要求您输出满足该属性的所有对，我认为没有什么比 O(N^2) 更好的了，因为输出中可以有 O(N^2) 对。
但这对于 x + y = z 也是如此，您声称有一个 O(N) 解决方案 - 所以我可能会遗漏一些东西。
我怀疑最初的问题是询问配对的数量。在这种情况下，它可以在 O(N log(N)) 中完成。对于每个元素 x 找出 y = z - x 并在数组中对 y 进行二进制搜索。y 的位置给出了可以用 x 的特定值形成的对数。将数组中的所有值相加即可得出答案。有 N 个值，如果每个对需要 O(log(N))（二分搜索），则找到数量，所以整个事情是 O(N log(N))。
于 2012-09-02T07:18:56.217 回答
1
因为它是一个排序的整数数组，所以可以使用二分查找算法，所以最好的是O(N)，最差的是O(N*logN)，平均情况也是O(N*logN)。
于 2012-09-02T07:21:00.203 回答
1
如果添加每个元素唯一的附加约束，您可以在 O(N) 中找到它们。
在找到所有 x+y==z 对之后，您知道对于满足该条件的每个 x 和 y，每个低于其对的索引的 x 或 y（选择一个）满足 x+y < z健康）状况。
实际上选择这些并输出它们需要 O(n^2)，但从某种意义上说，x+y==z 对是答案的压缩形式，以及输入。
（您可以将输入预处理为每个元素都是唯一的表单，以及出现次数的计数器。这将花费 O(N) 时间。您可以将此解决方案推广到未排序的数组，将时间增加到 O(nlogn) .)
说在与解的大小成线性比例的时间内找到对的理由：假设问题是“0 和给定输入 K 之间的整数是什么”？
于 2012-09-02T07:13:18.200 回答
0
您可以对数组进行排序，对于小于 z 的每个元素，使用二进制搜索 - 总 O(NlogN)。
总运行时间：O(|P| + NlogN)，其中 P 是结果对。
于 2012-09-02T08:30:12.320 回答
0
这个问题实际上存在一个 O(nlogn) 解决方案。我要做的（在首先检查我是否被允许这样做之后）是定义我的算法/函数的输出格式。
我会将其定义为一系列元素（S，T）。S - 数组中元素的位置（或其值）。T - 子数组 [0,T] 的位置。因此，例如，如果 T=3，则表示元素 S 与元素 0、1、2 和 3 组合满足所需条件。
总的结果是 O(nlogn) 运行时间和 O(n) 内存。
于 2016-03-17T10:51:38.903 回答