s*n
2 楼
this should be open. you can either use
inorder travesal of bst and sequantial scan of arry
or
use
search each element in arry in bst.
or use
inorder traversal of bst and binary search of array
【在 s**x 的大作中提到】
: one BST , one sorted array, 求交集。
: 怎么弄？ complexity?
: thx!
inorder travesal of bst and sequantial scan of arry
or
use
search each element in arry in bst.
or use
inorder traversal of bst and binary search of array
【在 s**x 的大作中提到】
: one BST , one sorted array, 求交集。
: 怎么弄？ complexity?
: thx!
s*n
3 楼
this should be open. you can either use
inorder travesal of bst and sequantial scan of arry
or
use
search each element in arry in bst.
or
inorder traversal of bst and binary search of array
【在 s**x 的大作中提到】
: one BST , one sorted array, 求交集。
: 怎么弄？ complexity?
: thx!
inorder travesal of bst and sequantial scan of arry
or
use
search each element in arry in bst.
or
inorder traversal of bst and binary search of array
【在 s**x 的大作中提到】
: one BST , one sorted array, 求交集。
: 怎么弄？ complexity?
: thx!
d*y
4 楼
C#
public List IntersectionOfBSTandSortedArray(int[] array, int index,
Tree root, List currIntersection)
{
if ( i<0 || i>= array.length || root == null)
{
return currIntersection;
}
currIntersection = IntersectionOfBSTandSortedArray(array, index, root.
left, currIntersection);
if ( root.value == array[index] )
{
currIntersection.add(array[index]);
return IntersectionOfBSTandSortedArray(array, index+1, root.right,
currIntersection);
}
else if ( root.value < array[index] )
{
return IntersectionOfBSTandSortedArray(array, index, root.right,
currIntersection);
}
else
{
return IntersectionOfBSTandSortedArray(array, index+1, root,
currIntersection);
}
}
public List
Tree root, List
{
if ( i<0 || i>= array.length || root == null)
{
return currIntersection;
}
currIntersection = IntersectionOfBSTandSortedArray(array, index, root.
left, currIntersection);
if ( root.value == array[index] )
{
currIntersection.add(array[index]);
return IntersectionOfBSTandSortedArray(array, index+1, root.right,
currIntersection);
}
else if ( root.value < array[index] )
{
return IntersectionOfBSTandSortedArray(array, index, root.right,
currIntersection);
}
else
{
return IntersectionOfBSTandSortedArray(array, index+1, root,
currIntersection);
}
}
d*y
5 楼
没想到可以binary search。学习了。
【在 s*****n 的大作中提到】
: this should be open. you can either use
: inorder travesal of bst and sequantial scan of arry
: or
: use
: search each element in arry in bst.
: or
: inorder traversal of bst and binary search of array
【在 s*****n 的大作中提到】
: this should be open. you can either use
: inorder travesal of bst and sequantial scan of arry
: or
: use
: search each element in arry in bst.
: or
: inorder traversal of bst and binary search of array
k*n
6 楼
You must be cautious and get enough information before giving an answer.
Such as, how large is the bst and the array, is the bst balanced ...
After all, the BST provides no more information than a sorted array.
So this problem is just the same as "intersection of two sorted arrays"
which should be easy to answer...
【在 s**x 的大作中提到】
: one BST , one sorted array, 求交集。
: 怎么弄？ complexity?
: thx!
Such as, how large is the bst and the array, is the bst balanced ...
After all, the BST provides no more information than a sorted array.
So this problem is just the same as "intersection of two sorted arrays"
which should be easy to answer...
【在 s**x 的大作中提到】
: one BST , one sorted array, 求交集。
: 怎么弄？ complexity?
: thx!
c*t
7 楼
问两个相关的问题：
1. BST里能有重复的数吗？
2. in general case, 你说的"intersection of two sorted arrays"
题中， 每个sorted array里有没有重复的数？比如可以是 A[]= {2, 3, 3, 4, 5, 5,
6, 10, 12}吗？如果可以有重复的，那么在最终生成的结果的数组中是不是还有可能有
重复的数？
谢谢！
【在 k****n 的大作中提到】
: You must be cautious and get enough information before giving an answer.
: Such as, how large is the bst and the array, is the bst balanced ...
: After all, the BST provides no more information than a sorted array.
: So this problem is just the same as "intersection of two sorted arrays"
: which should be easy to answer...
1. BST里能有重复的数吗？
2. in general case, 你说的"intersection of two sorted arrays"
题中， 每个sorted array里有没有重复的数？比如可以是 A[]= {2, 3, 3, 4, 5, 5,
6, 10, 12}吗？如果可以有重复的，那么在最终生成的结果的数组中是不是还有可能有
重复的数？
谢谢！
【在 k****n 的大作中提到】
: You must be cautious and get enough information before giving an answer.
: Such as, how large is the bst and the array, is the bst balanced ...
: After all, the BST provides no more information than a sorted array.
: So this problem is just the same as "intersection of two sorted arrays"
: which should be easy to answer...
k*n
8 楼
,
Yes, you can set a flag to put the duplicated number to left or right child
and flip the flag each time, thus keep the BST more likely to be balanced.
I won't consider that at first, since it matters only to personal choices...
even there are duplicates, the whole algorithm won't change, and the
complexity
wont change, except for extreme cases...
【在 c*********t 的大作中提到】
: 问两个相关的问题：
: 1. BST里能有重复的数吗？
: 2. in general case, 你说的"intersection of two sorted arrays"
: 题中， 每个sorted array里有没有重复的数？比如可以是 A[]= {2, 3, 3, 4, 5, 5,
: 6, 10, 12}吗？如果可以有重复的，那么在最终生成的结果的数组中是不是还有可能有
: 重复的数？
: 谢谢！
s*x
9 楼
what is complexity in 3rd solution? I am not sure.
【在 s*****n 的大作中提到】
: this should be open. you can either use
: inorder travesal of bst and sequantial scan of arry
: or
: use
: search each element in arry in bst.
: or
: inorder traversal of bst and binary search of array
【在 s*****n 的大作中提到】
: this should be open. you can either use
: inorder travesal of bst and sequantial scan of arry
: or
: use
: search each element in arry in bst.
: or
: inorder traversal of bst and binary search of array
f*4
10 楼
If the BST has parent pointer, you can find the smallest element, then use
next_element() to iterate BST.
In the same time you can iterate the array. Compare the current node and
current index, if same, you find intersection. Otherwise if current index is
bigger, iterate BST. Otherwise increase current index. Stop when tree is
iterated or array is iterated.
No matter they have duplicate elements or tree is very big, you have O(n)
speed with O(1) space
next_element() to iterate BST.
In the same time you can iterate the array. Compare the current node and
current index, if same, you find intersection. Otherwise if current index is
bigger, iterate BST. Otherwise increase current index. Stop when tree is
iterated or array is iterated.
No matter they have duplicate elements or tree is very big, you have O(n)
speed with O(1) space
c*t
11 楼
I feel your codes may only return an empty List. For the first recursion call
, it will end until root.left points to null, then return empty result.
【在 d********y 的大作中提到】
: C#
: public List IntersectionOfBSTandSortedArray(int[] array, int index,
: Tree root, List currIntersection)
: {
: if ( i<0 || i>= array.length || root == null)
: {
: return currIntersection;
: }
: currIntersection = IntersectionOfBSTandSortedArray(array, index, root.
: left, currIntersection);
, it will end until root.left points to null, then return empty result.
【在 d********y 的大作中提到】
: C#
: public List
: Tree root, List
: {
: if ( i<0 || i>= array.length || root == null)
: {
: return currIntersection;
: }
: currIntersection = IntersectionOfBSTandSortedArray(array, index, root.
: left, currIntersection);
c*t
12 楼
Great!
Let's assume bst contains m nodes and array has n elements.
For each of your solution, the complexity is
1.inorder travesal of bst and sequantial scan of arry
O(m+n)
2.use search each element in arry in bst.
O(n*lg(m))
3.use inorder traversal of bst and binary search of array
O(m*log(n))
Am I right?
【在 s*****n 的大作中提到】
: this should be open. you can either use
: inorder travesal of bst and sequantial scan of arry
: or
: use
: search each element in arry in bst.
: or
: inorder traversal of bst and binary search of array
Let's assume bst contains m nodes and array has n elements.
For each of your solution, the complexity is
1.inorder travesal of bst and sequantial scan of arry
O(m+n)
2.use search each element in arry in bst.
O(n*lg(m))
3.use inorder traversal of bst and binary search of array
O(m*log(n))
Am I right?
【在 s*****n 的大作中提到】
: this should be open. you can either use
: inorder travesal of bst and sequantial scan of arry
: or
: use
: search each element in arry in bst.
: or
: inorder traversal of bst and binary search of array
w*3
13 楼
我觉得可以recursively
binary search root at the array
case1：Found in ith
//add ary[i] into rst
solve(tn root.left, ary, start, i)
solve(tn root.right, ary, i+1, end)
case 2: Not found
2.1 between i -1 and i element
solve(tn root.right, ary, i, end)
solve(tn root.left, ary, start, i)
2.2 smaller than start th element
solve(tn root.right, ary, start, end)
2.3 bigger than (end th - 1) element
solve( tn root.left, ary, start, end)
这样会不会快一点
binary search root at the array
case1：Found in ith
//add ary[i] into rst
solve(tn root.left, ary, start, i)
solve(tn root.right, ary, i+1, end)
case 2: Not found
2.1 between i -1 and i element
solve(tn root.right, ary, i, end)
solve(tn root.left, ary, start, i)
2.2 smaller than start th element
solve(tn root.right, ary, start, end)
2.3 bigger than (end th - 1) element
solve( tn root.left, ary, start, end)
这样会不会快一点
s*x
14 楼
for 3), mlogn, seems you just do binay search in array for each node.
however, I think you do not need to do a full binary search, only on half of
it once a parent node search is done.
so I think it should be less than mlogn, but can not figure out what it
should be. :(
【在 c********t 的大作中提到】
: Great!
: Let's assume bst contains m nodes and array has n elements.
: For each of your solution, the complexity is
: 1.inorder travesal of bst and sequantial scan of arry
: O(m+n)
: 2.use search each element in arry in bst.
: O(n*lg(m))
: 3.use inorder traversal of bst and binary search of array
: O(m*log(n))
: Am I right?
however, I think you do not need to do a full binary search, only on half of
it once a parent node search is done.
so I think it should be less than mlogn, but can not figure out what it
should be. :(
【在 c********t 的大作中提到】
: Great!
: Let's assume bst contains m nodes and array has n elements.
: For each of your solution, the complexity is
: 1.inorder travesal of bst and sequantial scan of arry
: O(m+n)
: 2.use search each element in arry in bst.
: O(n*lg(m))
: 3.use inorder traversal of bst and binary search of array
: O(m*log(n))
: Am I right?
c*p
15 楼
find_union(BST_node* root, int * array, int array_start, int array_end, int*
union)
{
if(root == NULL)
return;
if(array_start > array_end)
return;
val = root->key;
pos = array.find(val, array_start, array_end);
if(array[pos] == val)
union.push(val);
find_union(root->left, array, array_start, pos - 1, union);
find_union(root->right, array, pos + 1, array_end, union);
}
其中array.find()应当返回“>= val的最小元素”或者“<=val的最大元素”的下标
union用vector/linklist比较好，懒得改了。
可能还会有BUG，欢迎拍砖。
【在 s**x 的大作中提到】
: one BST , one sorted array, 求交集。
: 怎么弄？ complexity?
: thx!
union)
{
if(root == NULL)
return;
if(array_start > array_end)
return;
val = root->key;
pos = array.find(val, array_start, array_end);
if(array[pos] == val)
union.push(val);
find_union(root->left, array, array_start, pos - 1, union);
find_union(root->right, array, pos + 1, array_end, union);
}
其中array.find()应当返回“>= val的最小元素”或者“<=val的最大元素”的下标
union用vector/linklist比较好，懒得改了。
可能还会有BUG，欢迎拍砖。
【在 s**x 的大作中提到】
: one BST , one sorted array, 求交集。
: 怎么弄？ complexity?
: thx!
s*x
16 楼
差不多就这样，你认为 这个 complexity 是多少？
int*
【在 c****p 的大作中提到】
: find_union(BST_node* root, int * array, int array_start, int array_end, int*
: union)
: {
: if(root == NULL)
: return;
: if(array_start > array_end)
: return;
: val = root->key;
: pos = array.find(val, array_start, array_end);
: if(array[pos] == val)
int*
【在 c****p 的大作中提到】
: find_union(BST_node* root, int * array, int array_start, int array_end, int*
: union)
: {
: if(root == NULL)
: return;
: if(array_start > array_end)
: return;
: val = root->key;
: pos = array.find(val, array_start, array_end);
: if(array[pos] == val)
c*p
17 楼
不知道。。。。
【在 s**x 的大作中提到】
: 差不多就这样，你认为 这个 complexity 是多少？
:
: int*
【在 s**x 的大作中提到】
: 差不多就这样，你认为 这个 complexity 是多少？
:
: int*
s*d
18 楼
lg(n)^2 ?
【在 c****p 的大作中提到】
: 不知道。。。。
【在 c****p 的大作中提到】
: 不知道。。。。
d*y
19 楼
这里面确实有个bug。
数组的指标没有真的更新。
改成pass by reference应该就可以了。
call
【在 c********t 的大作中提到】
: I feel your codes may only return an empty List. For the first recursion call
: , it will end until root.left points to null, then return empty result.
数组的指标没有真的更新。
改成pass by reference应该就可以了。
call
【在 c********t 的大作中提到】
: I feel your codes may only return an empty List. For the first recursion call
: , it will end until root.left points to null, then return empty result.
k*n
20 楼
no way, eventually you must visit every node of bst,
so cannot be less than something times n.
by master theorem, set both bst and tree sizes n
it should be
f(n) = 2*f(n/2)+lgn
so a=2, b=2 and n^(log_b~a) = n, case 1 applies
f(n) = O(n)
which is as good as in-order traversal plus array cursor.
If you don't remember master theorem, think this way:
for the leaf nodes, you do binary search in every section of array,
about 1/2 times leaf nodes of binary searches in the second level,
... ..., this makes you recall bottom-up heapify, right?
So the complexity is O(n).
【在 s*****d 的大作中提到】
: lg(n)^2 ?
so cannot be less than something times n.
by master theorem, set both bst and tree sizes n
it should be
f(n) = 2*f(n/2)+lgn
so a=2, b=2 and n^(log_b~a) = n, case 1 applies
f(n) = O(n)
which is as good as in-order traversal plus array cursor.
If you don't remember master theorem, think this way:
for the leaf nodes, you do binary search in every section of array,
about 1/2 times leaf nodes of binary searches in the second level,
... ..., this makes you recall bottom-up heapify, right?
So the complexity is O(n).
【在 s*****d 的大作中提到】
: lg(n)^2 ?
c*t
21 楼
Sorry for my poor math, I can't understand it. However, I feel it is
impossible to be O(n). Since traveling the whole bst needs O(n) and
searching the sorted array can not be O（1）.
I think it is less than m*lg(n), because it doesn't need to search the whole
array every time.
For example, if bst is 2,7,9 and array is 1,2,3,4,5, when the tree node 2
has been found in the array, then the next time, it only needs to start from
3 to search the array.
Giving an extreme example, if bst is 1,2,3,4,5,6 and array is also 1,2,3,4,5
,6, it is easy to find out the average elements search in the array is the
half of its length, so the complexity is m*lg(n/2) = m*(lg(n)-1).
For general cases, if the integer numbers are random or distributed in both
bst and array, the complexity should be about the same, O(m*(lg(n)-1)).
【在 k****n 的大作中提到】
: no way, eventually you must visit every node of bst,
: so cannot be less than something times n.
: by master theorem, set both bst and tree sizes n
: it should be
: f(n) = 2*f(n/2)+lgn
: so a=2, b=2 and n^(log_b~a) = n, case 1 applies
: f(n) = O(n)
: which is as good as in-order traversal plus array cursor.
: If you don't remember master theorem, think this way:
: for the leaf nodes, you do binary search in every section of array,
impossible to be O(n). Since traveling the whole bst needs O(n) and
searching the sorted array can not be O（1）.
I think it is less than m*lg(n), because it doesn't need to search the whole
array every time.
For example, if bst is 2,7,9 and array is 1,2,3,4,5, when the tree node 2
has been found in the array, then the next time, it only needs to start from
3 to search the array.
Giving an extreme example, if bst is 1,2,3,4,5,6 and array is also 1,2,3,4,5
,6, it is easy to find out the average elements search in the array is the
half of its length, so the complexity is m*lg(n/2) = m*(lg(n)-1).
For general cases, if the integer numbers are random or distributed in both
bst and array, the complexity should be about the same, O(m*(lg(n)-1)).
【在 k****n 的大作中提到】
: no way, eventually you must visit every node of bst,
: so cannot be less than something times n.
: by master theorem, set both bst and tree sizes n
: it should be
: f(n) = 2*f(n/2)+lgn
: so a=2, b=2 and n^(log_b~a) = n, case 1 applies
: f(n) = O(n)
: which is as good as in-order traversal plus array cursor.
: If you don't remember master theorem, think this way:
: for the leaf nodes, you do binary search in every section of array,
k*n
22 楼
Master theorem wont lie...
Really think about the bottom-up heapify example.
the root element needs lgn siftdown, the two child need lgn-1 siftdown, ...
how can the whole operation takes O(n)?
of coz if m and n differ a lot, that's another story,
suppose array size m is much bigger.
At the leaves level, in total n binary searches are done on average m/n
segments, that is log(m/n) each, so its n log(m/n)
at its upper level, n/2 binary searches on segments sized 2m/n,
it's nlog(m/n)* (log2/2) = n log(m/n) * 1/2 consider base 2
so it's still similar with the array size n case,
only differs at a log(m/n) constant, resulting in O(nlog(m/n))
whole
from
,5
【在 c********t 的大作中提到】
: Sorry for my poor math, I can't understand it. However, I feel it is
: impossible to be O(n). Since traveling the whole bst needs O(n) and
: searching the sorted array can not be O（1）.
: I think it is less than m*lg(n), because it doesn't need to search the whole
: array every time.
: For example, if bst is 2,7,9 and array is 1,2,3,4,5, when the tree node 2
: has been found in the array, then the next time, it only needs to start from
: 3 to search the array.
: Giving an extreme example, if bst is 1,2,3,4,5,6 and array is also 1,2,3,4,5
: ,6, it is easy to find out the average elements search in the array is the
Really think about the bottom-up heapify example.
the root element needs lgn siftdown, the two child need lgn-1 siftdown, ...
how can the whole operation takes O(n)?
of coz if m and n differ a lot, that's another story,
suppose array size m is much bigger.
At the leaves level, in total n binary searches are done on average m/n
segments, that is log(m/n) each, so its n log(m/n)
at its upper level, n/2 binary searches on segments sized 2m/n,
it's nlog(m/n)* (log2/2) = n log(m/n) * 1/2 consider base 2
so it's still similar with the array size n case,
only differs at a log(m/n) constant, resulting in O(nlog(m/n))
whole
from
,5
【在 c********t 的大作中提到】
: Sorry for my poor math, I can't understand it. However, I feel it is
: impossible to be O(n). Since traveling the whole bst needs O(n) and
: searching the sorted array can not be O（1）.
: I think it is less than m*lg(n), because it doesn't need to search the whole
: array every time.
: For example, if bst is 2,7,9 and array is 1,2,3,4,5, when the tree node 2
: has been found in the array, then the next time, it only needs to start from
: 3 to search the array.
: Giving an extreme example, if bst is 1,2,3,4,5,6 and array is also 1,2,3,4,5
: ,6, it is easy to find out the average elements search in the array is the
相关阅读
on-site求祝福求内部推荐：Google, Bloomberg, MicrosoftH1b renewal， H4在国内怎么办？是不是没戏了？email附过来的offer能收回吗？银行类的公司如果没有当天或者隔天给offer是不是就悬了？A design question大陆25岁女公务员自曝真实收入 你们羡慕吗？zz (转载)HR说周一给通知，到现在也没有消息。when can you apply for OPT?下周onsite，求bless 加问题请问什么是 employee at willstock option 是怎么回事？还要买的那里能查到雇主是否e-verify?报个口头offer，该从不？众PhD毕业是坚持大致原方向找工作还是直接码工了事？TSC opt三月初的有多少没批的各位收到Google offer的 Intern，你们的推荐人被联系了没有？能不能有点离奇的点子CLRS上的红黑树题 13.3-6