x***i
发帖数: 72 | 1 给一列整数，比如［5 6 1 2 4 3］， 和两个整数，
求的是， 如果先把这一列整数构造成BST， 那么所给的这两个整数的距离 （就是从一
个点走到另一个点经过的边的数目）
比如，给的数是2，6， 那么久返回3
我的做法很普通，就是一个一个整数的插入，生成bst, 然后求两个点的距离（可以先
求lowest ancestor)
但是结果11个test case只通过了8， 不知道是什么test case
整数在0和2^31之间， 整数的数量最多是2^31
请大侠直接，哪里可以优化
update:
谢谢大家回复
其实我的问题是，
有没有不explicitly构造bst也能求解 的办法。 如果input是2^31个integer的话，那
么我的bst就需要2^31 * 12(一个integer加上2个pointer）的memory, 这个大概是24g
，还是最保守的估算。是不是这样用的heap 内存太大，导致大的test case 不过？ |
b********6
发帖数: 35437 | 2 After constructing the BST, you just need to find the common ancestor.
There is a similar problem on Leetcode |
m*******n
发帖数: 6660 | 3 你先搜到lowest common ancestor，然后从common ancestor开始再求距离试试？ |
s*******n
发帖数: 4 | |
m*******n
发帖数: 6660 | 5 共同先祖可以包括本身的。只要判断2个不同时大于或小于root就行。
【在 s*******n 的大作中提到】
: 没考虑一个是另一个的祖先的情况吧
|
x***i
发帖数: 72 | 6 这些我都考虑到了
【在 m*******n 的大作中提到】
: 共同先祖可以包括本身的。只要判断2个不同时大于或小于root就行。
|
a****i
发帖数: 1182 | 7 有哪些test没过？
【在 x***i 的大作中提到】
: 这些我都考虑到了
|
x***i
发帖数: 72 | 8 这个不知道，不给看
【在 a****i 的大作中提到】
: 有哪些test没过？
|
b********6
发帖数: 35437 | 9 You probably do not need to construct the BST, and need to use property of
BST to figure out the result.
You know the root value and two points value, so you can traverse the array
from left to right to find the lowest ancestor without actually construct
BST.
To find the distance from ancestor to a node, you can also use the property
of BST.
So it can be an one pass in place solution. |
n*****x
发帖数: 686 | 10 写了一下。不用build tree，找ancestor，求p和q到ancestor的距离即可，只是corner
case实在多，发现bug记得告诉我一声
int BST_distance(vector& nums, int p, int q){
if (p>q) return BST_distance(nums,q,p);
int ancestor=-1, grandpa=-1;
bool left;
for (int i=0; i
if (nums[i]>=p && nums[i]<=q){
ancestor=i;
for (int j=i-1, dist=INT_MAX; j>=0; j--){
if (abs(nums[j]-nums[i])
if (nums[j]>nums[i]) left=true;
else left=false;
grandpa = nums[j];
dist = abs(nums[j]-nums[i]);
}
}
break;
}
}
int distp=0, distq=0;
bool reach_p=false, reach_q=false, flag_p=false, flag_q=false;
int turn_p=0, turn_q=0, prev_p=nums[ancestor], prev_q=nums[ancestor];
for (int i=ancestor; i
if (nums[i]<=nums[ancestor] && !reach_p){
if (!left && nums[i]
continue;
if (!flag_p) {
if (nums[i]<=prev_p) {
distp++;
prev_p = nums[i];
}
if (nums[i]
turn_p=nums[i];
flag_p=true;
}
}
else {
if (nums[i]>turn_p && nums[i]<=p) distp++;
}
}
if (nums[i]>=nums[ancestor] && !reach_q){
if (left && nums[i]>grandpa && i!=ancestor && ancestor!=0)
continue;
if (!flag_q) {
if (nums[i]>=prev_q){
distq++;
prev_q = nums[i];
}
if (nums[i]>q) {
turn_q=nums[i];
flag_q=true;
}
}
else {
if (nums[i]=q) distq++;
}
}
if (nums[i]==p) reach_p=true;
if (nums[i]==q) reach_q=true;
if (reach_p && reach_q) break;
}
return distp+distq-2;
} |
l******f
发帖数: 19 | |
c*g
发帖数: 634 | 12 这道题和哪个lc的题相似？
难道和bst如何建的没有关系吗？2到6难道不是4？
3，1，2，4，5，6 |
