我想知道我是否可以得到一些帮助。我想找到一种算法,即 THETA(n) 或线性时间,用于确定 2 个排序数组中的 2 个数字是否加起来等于某个数字。
例如,假设我们有 2 个排序数组:X 和 Y
我想确定是否有 X 的一个元素和 Y 的一个元素相加正好等于某个数字,比如 50。
到目前为止,我已经能够在 Python 中提出这些算法,但我很确定它们是 THETA(n^2) 的阶数而不是 THETA(n)。
def arrayTestOne(X,Y):
S =[1 for x in X for y in Y if x+y == 50]
def arrayTestTwo(X,Y):
for x in X:
for y in Y:
if x + y == 50:
print("1")
我认为是双 for 循环打破了线性时间,但您还能如何遍历 2 个列表?如有任何想法,我们将不胜感激。
最佳答案
您可以做的是从一个列表中的最高值和另一个列表中的最低值开始,然后检查总和。
如果总和是您的目标,那么您就完成了。
如果它太高,转到第一个列表中的下一个最高值。
如果它太低,则转到第二个下一个最低值。
如果您通过两个列表都没有到达目标,则返回 false。
关于python - 两个排序数组,2个元素的总和等于某个数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39581834/