一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 776|回复: 19
收起左侧

[CareerCup] 【第三轮】7.7-7.13 CareerCup 4.3

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-7-6 20:51:59 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
4.3 Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。


grassgigi 发表于 2014-7-7 01:02:12 | 显示全部楼层
【解题思路】
Recursively created bst whose root is the mid point of lo and hi elements in array

【时间复杂度】
since O(N) = 2 * O(N/2) + O(1)
=> O(lgN) - N is # of elements in array

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/chrislukkk/be47c3281a3911c10475
BST: https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8

【test case】

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

ryancooper 发表于 2014-7-9 02:15:50 | 显示全部楼层
grassgigi 发表于 2014-7-7 01:02
【解题思路】
Recursively created bst whose root is the mid point of lo and hi elements in array

Your time complexity is not correct, it should be O(n). it can be deducted as follow:
lg(T(N)) = 1 + lg(T(N/2)) => lg(T(N)) = lgN => T(N) = N
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-10 01:52:41 | 显示全部楼层
【解题思路】优先取出中间值作为root,取出左半边的中间值作为root.left, 右半边为root.right,递归
程序参考了沙发的写法,非常漂亮的递归
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】
https://github.com/donnice/donnice/blob/master/Q4_3
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-11 00:01:20 | 显示全部楼层
【解题思路】recursion, ref to the 2nd
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】https://gist.github.com/bitcpf/7c5d19d378c7a595ef57
回复 支持 反对

使用道具 举报

Neal 发表于 2014-7-11 08:34:15 | 显示全部楼层
【解题思路】divid and conquer.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】https://gist.github.com/nealhu/5580fa4178d2e81528df
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-11 13:07:05 | 显示全部楼层
【解题思路】Binary search.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/471a22c93c3f65a663c6
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-7-11 20:28:06 | 显示全部楼层
【解题思路】
recursion. 将array [low,...,mid-1, mid, mid+1,... high]分成3个部分[low,...,mid-1], [mid] 和[mid+1,...,high],对于当前node,放入[mid], 然后将[low,...,mid-1]的中位数放入node.left,将[mid+1,...,high]的中位数放入node.right
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/chouclee/683394edb16d86949ce8
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-11 23:11:03 | 显示全部楼层
【解题思路】
recursion


【时间复杂度】
O(n)

【空间复杂度】
O(logn)

【gist link】
https://gist.github.com/happyWinner/cffc5643c6e013b7470f




评分

1

查看全部评分

回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-11 23:13:16 | 显示全部楼层
为什么楼上的你们的空间复杂度都是O(n)?不应该是O(log n)么
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-11 23:35:03 | 显示全部楼层
圆梦梦剧场 发表于 2014-7-11 23:13
为什么楼上的你们的空间复杂度都是O(n)?不应该是O(log n)么

因为 虽然递归用了logN的空间
但是返回值,也就是建立好的tree占用了O(n)的空间
所以总的空间复杂度应该还是O(n)
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-12 03:20:05 | 显示全部楼层
【解题思路】bst, 从中间取,左右各为一半,计算
【时间复杂度】o(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/hilda8519/60367ae3e1a6b4dc0c49
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-7-12 03:58:04 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-13 03:44:07 | 显示全部楼层
【解题思路】
recursively create sub-trees, return pointer to the root. return null pointer when start and end pointer overlaps.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/befe79a84c97f985489f
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-13 08:53:36 | 显示全部楼层
【解题思路】
recursively create sub-trees, return pointer to the root.
return null pointer when start and end pointer overlaps.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/JoyceeLee/627488dd7113966bfd92
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-14 05:45:05 | 显示全部楼层
【解题思路】
since we are creating BST from sorted array, the middle element of the array is the root of the BST. using divide and conquer to build the left and right subtree from left and right subarray.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/3b0c485726cd15632bef
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-15 15:46:33 | 显示全部楼层
【解题思路】recursive solution. The middle element should be the root of the tree, the left half be the left subtree and the right half become to the right subtree
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】https://gist.github.com/jyhjuzi/8af477cdc9f92a57d842
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 04:37:37 | 显示全部楼层
【解题思路】 recursion: add the middle number first, then access left haft and right half.
值得注意的是最后一个元素会被漏掉,在第归出口判断一下就行了
懒得建树了,最后只把建树的顺序存在了一个queue里

【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】https://gist.github.com/Noahsark/067a9ff44fe49274788d

回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2014-7-19 22:20:03 | 显示全部楼层

【解题思路】recursive solution. The middle element should be the root of the tree, the left half be the left subtree and the right half become to the right subtree
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】 https://gist.github.com/xun-gong/bcc74b741c02535a5d1e
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 16:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表