这是一个面试问题。给定一个已排序的整数数组和数字z，在数组中找到所有满足x+y<z的对(x,y)。是否可以比O(n^2)更好地完成？
P.S. 我知道我们可以在O(N)的时间内找到所有满足x+y==z的对(x,y)。
7个回答
9
你不能保证在O(n)时间内找到所有具有此属性的值对，因为可能存在O(n2)个这样的值对。一般来说，算法运行所需的时间不会少于它产生的值的数量。
希望这可以帮到你！
- templatetypedef
1
虽然我完全同意你的观察，但请看一下我的评论，关于我们能否自己定义输出“格式”的能力。 - ZeDuS
5
在通常情况下，不能。考虑这样一种情况：x + y < z 对于数组中的所有x和y都成立。您必须触及（例如显示）集合中可能的n(n-1)/2对。这是基本上是O(n^2)。
- CB Bailey
2
如果要输出所有满足该属性的配对，我认为没有比O(N^2)更好的方法，因为输出中可能有O(N^2)个配对。
但是对于x + y = z，你声称有一个O(N)的解决方案，这也是正确的-所以我可能漏掉了什么。
我怀疑原始问题是要求配对数。在这种情况下，可以在O(N log(N))内完成。对于每个元素x，找出y = z-x，并在数组中进行二进制搜索。 y的位置给出了可以与该特定值的x形成的配对数。将这个值加起来就得到了答案。有N个值，每个值找到配对数需要O(log(N))（二进制搜索），所以整个过程是O(N log(N))。
但是对于x + y = z，你声称有一个O(N)的解决方案，这也是正确的-所以我可能漏掉了什么。
我怀疑原始问题是要求配对数。在这种情况下，可以在O(N log(N))内完成。对于每个元素x，找出y = z-x，并在数组中进行二进制搜索。 y的位置给出了可以与该特定值的x形成的配对数。将这个值加起来就得到了答案。有N个值，每个值找到配对数需要O(log(N))（二进制搜索），所以整个过程是O(N log(N))。
- MAK
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之间的整数是什么”？
- user684934
1
因为这是一个排序的整数数组，所以可以使用二分查找算法，最好的情况是
O(N)，最坏的情况是O(N*logN)，平均情况也是O(N*logN)。- xdazz
0
你可以对数组进行排序，对于每个小于z的元素，使用二分查找-总共O(NlogN)。
总运行时间：O（|P| + NlogN），其中P是结果对。
- barak1412
0
这个问题实际上存在一个O(nlogn)的解决方案。 我会在首先检查是否允许的情况下，定义算法/函数的输出格式。
我会将其定义为元素(S,T)的序列。S-数组中元素的位置(或其值)。T-子数组[0,T]的位置。例如，如果T=3，则意味着元素S与元素0、1、2和3组合满足所需条件。
总体结果是O(nlogn)运行时间和O(n)内存。
- ZeDuS
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 4 如何将Numpy数组从(x,y,z)重塑为(y,z,x)？
- 5 三个正整数 x、y、z 的组合，使得 x + y、x - y、y + z、y - z、x + z 和 x - z 都是完全平方数。
- 5 通过一个三维数据数组获取 x、y、z 的均值
- 3 如何将[].concat（["x", "y"]，"z"）的结果变为[["x"，"y"]，"z"]，而不是["x"，"y"，"z"]？该问题涉及IT技术。
- 3 寻找所有满足 x² + y² = z² + u² 的数组中的数字的 O(n² log(n)) 算法
- 17 在一个已排序的数组中找到小于 x 的最大值。
- 3 按照X、Y或Z值排序点云坐标
- 3 使用name[x,y]而不是name[x][y]的数组写法
- 7 简化Z = X ^ (X << Y)函数的反函数
- 12 如何枚举满足附加约束条件的 x^2 + y^2 = z^2 - 1？