1. 首页
  2. 问答
  3. 查找排序数组中的所有对（x，y），以便x + y <z

查找排序数组中的所有对（x，y），以便x + y <z

2012-09-02 131 views

回答

8

你一定不能找到o所有这些成对的（N ）的时候，因为有可能是为O（n ）对有此属性的值。一般来说，算法运行所花费的时间不会少于所产生的值的数量。

希望这会有所帮助！

来源

2012-09-02 07:05:55 templatetypedef

+0

尽管我完全同意你的观察，请参阅我对我们自己定义输出“格式”的能力的评论。 – ZeDuS

5

在产生，没有它做不到。考虑数组中的所有x,y的x + y < z的情况。您必须触摸（例如显示）该组中所有可能的n(n - 1)/2对。这基本上是O（n^2）。

来源

2012-09-02 07:06:24

1

你可以找到他们在O（N），如果你添加额外的约束，每个元素是唯一的。

找到所有的x + y == z对之后，您知道对于满足该条件的每个x和y，每个x或y（选择一个）处于比其对的索引更低的索引满足x + y < z条件。

实际上选择这些和输出它们将需要为O（n^2），但在某种意义上，X + Y ==Ž对是答案的压缩形式，与输入到一起。您可以将输入预处理为每个元素都是唯一的表单，以及计数器的出现次数，这需要O（N）次。您可以将此解决方案推广到未排序的数组，从而增加O（nlogn）。）

说明在时间之下找到对与解的大小成线性比例的理由：假设问题是“什么是介于0和给定输入K之间的整数” ？

来源

2012-09-02 07:13:18 bdares

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-02 07:18:56 MAK

1

因为它是一个分类整数数组，你可以使用二进制搜索算法，所以最好是O(N)，而最糟糕的是O(N*logN)，平均情况下也O(N*logN)。

来源

2012-09-02 07:21:00 xdazz

0

您可以排序数组，并为每一个元素比小Z，使用二进制搜索 - 总O（NlogN）。

总运行时间：O（| P | + NlogN），其中P是结果对。

来源

2012-09-02 08:30:12 barak1412

0

这个问题实际上存在一个O（nlogn）解决方案。 我会做什么（首先检查是否允许我这样做）是定义我的算法/函数的输出格式。

我将它定义为一个元素序列（S，T）。 S - 数组中元素的位置（或其值）。 T - 子阵列的位置[0，T]。因此，例如，如果T = 3，则意味着与元素0,1,2和3结合的元素S满足期望的条件。

总的结果是O（nlogn）运行时间和O（n）内存。

来源

2016-03-17 10:51:38 ZeDuS

相关问题

 相关问题