see*_*ker 5 java algorithm big-o binary-search-tree data-structures
我正试图找到解决问题的方法
Find two elements in balanced BST which sums to a given a value.
约束时间O(n)和空间O(logn).
我想知道以下算法是否有效.
int[] findSum(Node root, int sum){
int[] sumArray;
for (int i=0;i<sum;i++) {
if (root.contains(i) && root.contains(sum-i)) {
sumArray[0] = i;
sumArray[1] = sum-i;
}
}
}
我明白我的方法可能是错的.我很感激我的伪代码/更好的算法的任何反馈/更正
我相信你的方法会有效,但没有适当的时间限制.
让我们从分析这种算法的复杂性开始.请注意,此处需要考虑两个不同的参数.首先,BST中有元素总数.如果使BST变大或变小,则算法完成所需的时间将更长或更短.我们把这个号码称为n.其次,您希望值总和的总数.我们称之为U值.
那么让我们看看你当前的算法是做什么的.现在,它迭代循环O(U)次,在每次迭代时检查BST中是否存在两个值.每次BST查找都需要时间O(log n),因此算法所做的总工作量为O(U log n).但是,您的算法仅使用常量空间(即空间O(1)).
不幸的是,这个运行时并不是很好.如果目标数量非常大(例如,1,000,000,000),那么您的算法将需要很长时间才能完成,因为U将会非常大.
所以现在的问题是如何更有效地解决这个问题.幸运的是,我们可以使用一种非常可爱的算法来解决问题,并且它将利用BST元素按排序顺序存储的事实.
让我们首先解决一个类似的问题,这个问题与你提出的问题有点不同.假设,而不是给你一个BST和目标号码,我给你一个排序的数组和对象号码,然后问同样的问题:是否有两个数字在此有序阵列总结的目标是什么？例如,我可能会给你这个数组:
0 1 3 6 8 9 10 14 19
假设你想知道这个数组中的两个数字总和是16.你怎么能这样做？
您可以尝试以前使用的相同方法:检查数组是否包含0和16,1和15,2和14等,直到找到一对或用完要检查的值.检查排序数组中是否存在元素需要使用二进制搜索时间O(log n),因此该算法仍需要O(U log n)时间.(如果你知道这些值很好地分布,你可以想象使用插值搜索来提高速度,这会在预期时给出O(U log log n)运行时,但是那个大U项仍然是个问题).
所以让我们考虑一种不同的方法.从根本上说,你在做什么,你需要明确枚举总结到U.但是,所有的对,其中大部分都没有去那里,而且,事实上,大部分时间都不在对元素将在那里.通过使用以下算法,我们可以更快地完成任务:
该算法将要求您查看数组中的总共O(n)个元素,每次执行O(log n)工作以查找匹配对.在这种最坏的情况下,这将花费O(n log n)时间并使用O(1)空间.如果U是一个庞大的数字,这比以前要好得多,因为根本不再依赖于U!
但是,通过巧妙地观察问题的结构,我们可以进一步加快速度.让我们假设我们正在查看数组中的数字x并进行二进制搜索以查找U - x.如果我们找到它,我们就完成了.如果没有,我们会发现数组中的第一个数字大于U - x.我们称这个数字为z.
因此,现在假设我们想要查看数y是否可以是总和为U的对的一部分,而且,假设y大于x.在那种情况下,我们知道
y + z
> x + z
> x +(U - x)
= U.
这说的是y和z之和大于 U,所以它不可能是U.这是什么意思？好吧,我们通过尝试对与x配对的元素进行二进制搜索来找到z,总结为U.我们刚才展示的是,如果你尝试将z添加到数组中大于x的任何数字,总数必须超过U.换句话说,z不能与大于x的任何东西配对.类似地,任何大于z的东西都不能与大于x的任何东西配对,因为它必须总结为大于U的东西.
基于这种观察,我们可以尝试使用不同的算法.让我们像以前一样拿出我们的数组,看看我们是否能找到一个总和为16的对:
0 1 3 6 8 9 10 14 19
让我们保持两个指针 - 一个"左手侧"指针lhs和一个"右手侧"指针rhs:
0 1 3 6 8 9 10 14 19
^ ^
lhs rhs
当我们总结这两个数字时,我们得到19,超过U.现在,我们加起来的任何数字对都必须使其较低的数字至少与lhs数一样大,即0.因此,如果我们在这里总结了使用数字19的任何一对,我们知道总和太大了.因此,我们可以不考虑任何包含19的对.这就离开了
0 1 3 6 8 9 10 14 19
^ ^
lhs rhs
现在,看看这个总和(14),它太小了.使用与以前类似的逻辑,我们可以有把握地说,使用0的剩余数组中的任何总和必须最终给出小于16的总和,因为总和中的第二个数字最多为14.因此,我们可以排除0:
0 1 3 6 8 9 10 14 19
^ ^
lhs rhs
我们开始看到一种模式:
最终,我们将找到一对总和达到16的对,或者lhs和rhs会相互撞击,此时我们保证没有对总计达到16.
通过这个算法,我们得到了
0 1 3 6 8 9 10 14 19
^ ^
lhs rhs (sum is 15, too small)
0 1 3 6 8 9 10 14 19
^ ^
lhs rhs (sum is 17, too big)
0 1 3 6 8 9 10 14 19
^ ^
lhs rhs (sum is 13, too small)
0 1 3 6 8 9 10 14 19
^ ^
lhs rhs (sum is 16, we're done!)
瞧瞧!我们得到了答案.
那有多快？好吧,在每次迭代时,lhs下降或rhs上升,算法在相遇时停止.这意味着我们进行O(n)次迭代.每次迭代最多都是常量工作,因此每次迭代最多需要O(1)次工作.这给出了总时间复杂度O(n).
空间怎么样？好吧,我们需要存储两个指针,每个指针占用O(1)空间,因此总空间使用量为O(1).大!
但是这与你的问题有什么关系呢？连接是这样的:在每个时间点,该算法只需要记住数组中的两个数字.然后它需要能够从一个元素前进到下一个元素或从一个元素前进到前一个元素.这就是它必须做的一切.
因此,假设您使用二叉搜索树而不是使用排序数组.从两个指针开始,一个指向最小节点,一个指向最大节点.一旦你有这个设置,你可以模拟上面的算法,用" 移动到lhs的inorder后继 "和" 移动到rhs的inorder的前导 "替换"increment lhs"和"递减rhs" .可以实现这些操作,以便它们使用总共O(log n)空间(假设树是平衡的)并且使得每种类型的n个操作的任何序列总共花费O(n)时间(无论是否树是平衡的).因此,如果您使用上面修改的算法来处理BST,您将获得一个花费时间O(n)并仅使用O(log n)空间的算法!
实现细节有点棘手,我将把这一部分作为练习留给你.如果您不熟悉继任者和前任,那么网上有很多好的资源.它们是BST上的标准算法,对于了解它们非常有用.我还会将阵列算法正确性的正式证明作为练习,尽管它并不太难.
希望这可以帮助!