s**x
发帖数: 7506 | 1 one BST , one sorted array, 求交集。
怎么弄？ complexity?
thx! | s*****n
发帖数: 5488 | 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!
| s*****n
发帖数: 5488 | 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!
| d********y
发帖数: 2114 | 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);
}
} | d********y
发帖数: 2114 | 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
| k****n
发帖数: 369 | 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!
| c*********t
发帖数: 2921 | 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...
| k****n
发帖数: 369 | 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
发帖数: 7506 | 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
| f****4
发帖数: 1359 | 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 | | | c********t
发帖数: 5706 | 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);
| c********t
发帖数: 5706 | 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
| w*****3
发帖数: 101 | 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)
这样会不会快一点 | s**x
发帖数: 7506 | 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?
| c****p
发帖数: 6474 | 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!
| s**x
发帖数: 7506 | 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)
| c****p
发帖数: 6474 | 17 不知道。。。。
【在 s**x 的大作中提到】
: 差不多就这样，你认为 这个 complexity 是多少？
:
: int*
| s*****d
发帖数: 66 | 18 lg(n)^2 ?
【在 c****p 的大作中提到】
: 不知道。。。。
| d********y
发帖数: 2114 | 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.
| k****n
发帖数: 369 | 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 ?
| c********t
发帖数: 5706 | 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,
| k****n
发帖数: 369 | 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
|
|
