r****o
发帖数: 1950 | 1 感觉应该有类似binary search的方法, 复杂度O(lgn)，
但具体细节还是不清楚。
有谁知道怎么作吗？ |
|
l*****a
发帖数: 559 | 2 复习data structure时，发现插入后做rebalance需要height。网上能找到的getHeight
（）函数的时间复杂度是O（n）的。插入不可能做到O（lgn）。
public int getHeight ()
{
if (this.leftChild == null && this.rightChild == null)
{
return 0;
}
else
{
int leftH = 0;
int rightH = 0;
if (this.leftChild != null)
{
leftH++;
leftH += this.getLeftChild().getHeight();
}
if (this.rightChild != null)
... 阅读全帖 |
|
e*****r
发帖数: 93 | 3 getHeight复杂度是O(lgN)还有可以插入的时候就顺便更新了 |
|
a********r
发帖数: 217 | 4 假设BST每个key都是 >=0 的整数，而且不重复，有没有时间复杂度是O(lgn)的算法来
search kth smallest key. inorder traversal似乎不能满足要求。 |
|
r*******k
发帖数: 1423 | 5 不加信息是不可能的啊
如果有n个node，求第n个数，
你不遍历前n-1个数，你怎么知道哪个是第n个？
必然是o(n)啊
想到做lgn，必然不会遍历所有的，
剪枝需要额外的信息 |
|
j*******a
发帖数: 61 | 6 Thanks for all posts. Just want to confirm I understand right, let me repeat
your ideas.
Assume input: 4, -1, 5, 2, 0, -2.
looks for the closest sub array for 3
0 1 2 3 4 5 get sums sort BS for 3
------------------------------------
0 | 4 3 8 10 10 8 n nlgn lgn
1 | -1 4 6 6 4 lgn lgn
2 | 5 7 7 5 lgn lgn
3 | 2 2 0 lgn lgn
4 | 0 -2... 阅读全帖 |
|
h*******l
发帖数: 22 | 7 对静态interval set：（leetcode上的）
排序，nlgn
过一遍， n
动态的（不停有interval 插入）
方法一：
每个新的都插入到正确的位置，lgn
再过一遍，n
结果是n^2 的
方法2：
2.1 假设知道所有end points，比如1--1000000，每个点都是可能的endpoints
根据end point 建segment tree
每个新的插入需要lgn
总共nlgn
2.2 不知道end points
完全动态的segment tree，每次插入需要rebalance （O(1)）
修改union lgn
插入endpoints lgn
总共nlgn
这个就比较复杂了， 感觉面试仅停留于静态的就不错了
|
|
n*******w
发帖数: 687 | 8 不是。DP解是n * lgn
1. sort array by ending time （n*lgn time ）
2. 递归式
DP[i] = max { A[i].cost, DP[i-1], max { DP[k]+A[i].cost} }
k
max{k} where end time of A[k] <= start time of A[i]
n个subproblem，找k的时候可以binary search，lgn time
最后还是 n*lgn time
处理i的是时候有三种情况
1. 不使用A[i]
2. 使用A[i]，所以任意与A[i]有overlap的都要舍去，所以要找k
3. k找不到，因为A[i]的start time比第一个record的ending time都要小 |
|
n*******w
发帖数: 687 | 9 不是。DP解是n * lgn
1. sort array by ending time （n*lgn time ）
2. 递归式
DP[i] = max { A[i].cost, DP[i-1], max { DP[k]+A[i].cost} }
k
max{k} where end time of A[k] <= start time of A[i]
n个subproblem，找k的时候可以binary search，lgn time
最后还是 n*lgn time
处理i的是时候有三种情况
1. 不使用A[i]
2. 使用A[i]，所以任意与A[i]有overlap的都要舍去，所以要找k
3. k找不到，因为A[i]的start time比第一个record的ending time都要小 |
|
n****t
发帖数: 241 | 10 所以我一直没有想明白怎么样是lgn...
Sorry, even if u know the count of descent for each node, how can u achieve
O(lgN) with that info?
In the worst, case the bst is a sorted singly linked list. How can you get
the median of the SLL in O(lgN)?
Unless it's a balanced bst. But the condition is missing from your original
description, which is misleading. |
|
f*****w
发帖数: 2602 | 11 还不知道接下来结果怎么样 不过还是趁有空先回馈一下版面
第一次
居然是大牛Andrew Ng的学生；
为什么要FB
如果来了FB 最想做的事情 project 会是什么
然后问了个简历上的问题
然后 两个技术问题 很简单的
1. 实现一个strstr() 我说我可写不出KMP， 他说没事没事 就写个普通的就好
2. 给定一个没有通往父节点的连接的BST, 找到大于x的最小的那个节点。 我很stupid
地卡了很
久 最后给了一个不是很好的答案(O(lgn*lgn))。 他最后告诉我了更好的方法, 这个方
法确实比
我的好很多,lgN时间O(1)空间 就可以了。
我以为我挂了，但是有了第二次
这次好一些
1) 为什么FB
2) 简历上的好几个问题
3) 技术问题是找一个binary tree的叶子的最少depth。 我很stupid地给了个递归方法
。他说
不行啊， 要是很不balance的话，效率会很低。 我又很stupid的说那我会randomize每
次递归
的时候是左子树还是右子树，这样average 复杂度会低一些。
他忍无可忍了，说他expect something li... 阅读全帖 |
|
f****4
发帖数: 1359 | 12 这里就用树的中续遍历来说好了
如果是用stack的话，stack最长要能存储树的最长路径
最坏情况长度为n，最优为lgn
那么用递归的话，如果空间需要考虑stack的话，递归算不算inplace？
如果我们认为递归的stack开销不考虑，那么，我假设在这个树递归函数里面maintain
了一个local变量
那么因为这个函数在单核情况下，同一时间最多被调用n次，最少lgn次。那么这个算法
算是inplace么？（毕竟这里用到的额外内存为lgn ~ n 个）
还有，书上那个stack的分析是Amortized analysis
难道inplace也可以说是Amortized inplace?
sort |
|
f***s
发帖数: 112 | 13 大家给看看
1.对于N个数组的最大元素排序建二叉树，树除了左右指针还有一个指针指向对应的
ARRAY
2.取一个最大元素（最右叶节点），更新节点为对应次大值，摘除并且重新插入上面的
二叉树，直到K个值都被耗尽。（存在重新平衡树的要求）
3.重复2.）直到 m个节点都得到了返回。
复杂度 1） nlgn 2)单个需要 lgn 总体最坏 (m-1)lgn
加起来 O((m+n)lgn)
1.因为N个数组都是SORTED，每次取得单个数组的最大值是CONSTANT time
2 |
|
s****9
发帖数: 22 | 14 2sum目测可以lg n啊
lgn + 1/2 lgn + 1/4 lgn ... |
|
g**x
发帖数: 373 | 15 来自主题: JobHunting版 - 问到G家题 可以有O（lgN)的算法吗？
当BST为
1
2
3
4
...
如何O（lgN)呢？
在平均的情况下，in-order递归的方法也可以是O（lgN)，在worst情况下， 是O（N）。 |
|
e***r
发帖数: 68 | 16 看到关于2-3-4树的一个property: "Searches in N-node 2-3-4 tree visit at most
lgN+1 nodes."
我可以理解2-3-4树的高度at most是lgN+1,但不肯定visit过的node数目，因为对一个3
node或者4-node, 查找的时候需要访问的node数目可能超过一个，这时候也许树高减
少了，此消彼长，然后还是保持了lgN+1的upper bound.
想请教前辈们一个更rigid一点的解释。 |
|
p****s
发帖数: 3184 | 17 转帖微博
【谁才是主要敌人！——————呼啸山庄 ：今年，军费预算为7406亿人民币，每人
花600元保卫国家，这个我懂；维稳预算为7690亿人民币，每人花700元来对付自己，这
个我真的不懂.....！】
这是社会结构问题。中国树状社会结构(最高权力是根，像棵树一样铺开管制全国)在大
规模社会里效率奇低，因为每个管理操作的代价是O(lgn)。而英美的网络社会结构(节
点平权博弈、地方自治的契约社会，类Internet路由器组成的社会)是当时当地管理(
localized management)，代价是O(1)。长期看中国结构挺不住
我举个法律例子：一个大案，在英美是当地陪审团做出最终裁决，全是local
execution；而在中国，从地院上诉到中院，再到高院，还不行就到北京上访，维稳去
吧//中国树状社会结构在大规模社会里效率奇低，因为每个管理操作的代价是O(lgn)。
英美的网络社会结构是当时当地管理(localized mgmt)，代价是O(1) |
|
|
|
H*M
发帖数: 1268 | 20 a data structure augmented from red-black tree
also store the value in each node of the total number of elements of the
subtree (including that node itself)
insertion/deletion will be o(lgn)
getmedian will be o(lgn)
int |
|
H*M
发帖数: 1268 | 21 职业杯上的题是这样的:
Imagine you have a square matrix, where each cell is filled with either blac
k or white. Design an algorithm to find the maximum subsquare such that all
four borders are filled with black pixels.
不过按他的算法,我觉得是O(n^4)而不是O(n^2):
1. iterate each full column ->n
2. iterate each sub column -> n^2
3. check if it can form a sqaure ->n
total O(n^4)
第三步可以用2n个interval tree记录每行每列的连续0的起始index,这样第三步就省到
lgn,总共可以O(n^3.lgn). |
|
r****o
发帖数: 1950 | 22 Cong!
能不能说说两个sorted aray里面找第K大元素的O(lgn)算法的思路?
多谢。
签什么不许泄露题目的协议。而且大部分题目都是见过的。
换，index -> 数字，coding完，问测试。
word反转，另一个忘了。 套路都是先扯淡，再coding，再测试。
是话很多的人，所以面试超级没话讲。 对怎么测试俄罗斯方块这种题目测试毫无概念
，我怎么答面试官都不满意。。。 西雅图几天都是阴雨天气，预感肯定被拒。 果然
一周收到据信。
天没等到电话。 然后过了几天，没有任何通知，就打过来了。。面试官问我想不想面
，我想了一下，我的recruiter那么不靠谱，可能不会帮我重新安排，就硬头皮开始面。
后问了如何在2个排序好的数组里面找第K大的数。 我知道肯定要lgN的算法，但是一时
半会儿没想好怎么做。所以先写了个O(k)的简单版本。然后果然要求改进，我就开始写
logN的版本，最后写的八
solve问题的能力
是似乎他也没看出来。。 后来开始设计系统，非常发散的题目，讨论到了cache，
network, index， 因为和我做的东西有些相关，所以聊得很high |
|
r****o
发帖数: 1950 | 23 请问那个两个sorted array找第K大元素的O(lgn)算法怎么弄啊？
多谢。
签什么不许泄露题目的协议。而且大部分题目都是见过的。
换，index -> 数字，coding完，问测试。
word反转，另一个忘了。 套路都是先扯淡，再coding，再测试。
是话很多的人，所以面试超级没话讲。 对怎么测试俄罗斯方块这种题目测试毫无概念
，我怎么答面试官都不满意。。。 西雅图几天都是阴雨天气，预感肯定被拒。 果然
一周收到据信。
天没等到电话。 然后过了几天，没有任何通知，就打过来了。。面试官问我想不想面
，我想了一下，我的recruiter那么不靠谱，可能不会帮我重新安排，就硬头皮开始面。
后问了如何在2个排序好的数组里面找第K大的数。 我知道肯定要lgN的算法，但是一时
半会儿没想好怎么做。所以先写了个O(k)的简单版本。然后果然要求改进，我就开始写
logN的版本，最后写的八
solve问题的能力
是似乎他也没看出来。。 后来开始设计系统，非常发散的题目，讨论到了cache，
network, index， 因为和我做的东西有些相关，所以聊得很high |
|
x******3
发帖数: 245 | 24 第二题可以用balanced search tree, 比如RBT
在每个节点中保存以下信息
1) cache tag -> 查找O(lgn)
2) 以本节点为根的子树中最小recent used值 ->查找LRU O(lgn) |
|
x******3
发帖数: 245 | 25 感觉这个是对的， 但是这一步
combine with its adjacent elements in the
difference list, then update the min heap
应该不是O(lgN), 因为在heap中查找不是lgN
linked
in the |
|
r****o
发帖数: 1950 | 26 我对trie一直不是很懂，
如果要在n个单词中查某个单词(长度为m个字母)的话，
为什么不能把这n个单词组成一个binary search tree呢？这样平均复杂度是O(lgn)。
而用trie查的话复杂度是O(m)。
这样lgn
这个问题可能很弱，欢迎拍砖。 |
|
g*********s
发帖数: 1782 | 27 Sorry, even if u know the count of descent for each node, how can u achieve
O(lgN) with that info?
In the worst, case the bst is a sorted singly linked list. How can you get
the median of the SLL in O(lgN)?
Unless it's a balanced bst. But the condition is missing from your original description, which is misleading. |
|
g***s
发帖数: 3811 | 28 抛砖引玉一下：
解法一：
这题可以看作是二分图的最大匹配的最小值路径匹配问题。用KM算法可以知道O(N*M)=O
(N^3).
解法二：
分治法。找到两点，把所有点分成两部分，每个部分都用相同多的红点和蓝点。然后对
两部分分治。
如何找到这样的两点（先给一个nlgn的算法）
1. 找x值最小的一个点A（如果有多个x值相同，取y值最小），把它作为其中一点。
2. 把A作为原点。其它所有点对于A（都减去Ax,Ay)，都相当会落入第一和第四象限。
3. 把所有点求tan，排序。
4. 从小到大进行count，一直到找到这么一条边(A->B)。（易知一定存在这么一条边）
f(n) = max{ f(k) + f(n-k) + nlgn } k=1..n-1
f(n) = O(nlgn * n) = O(n^2 * lgn)
改进找B点的算法
3. 建立一最大堆，和一最小堆
4. 轮流从最大堆最小堆来进行查找，直到找到B
f(n) = max { f(k) + f(n-k) + (n + k*lgn)} k = 1..n/2
f(n) = O(n^2)
O(nlgn)感觉很难。 |
|
g**e
发帖数: 6127 | 29 linkedhashmap + max heap
put O(lgn) in worst case
get is O(1)
getMax is O(1)
to remvoe least recent use item, update heap may take O(lgn) worst case as
well. |
|
c*******n
发帖数: 63 | 30 1.sort three array first --> nlgn
2.1 form the first two elements --> n^2
2.2 find the third element of triplet --> lgn (binary search)
or as justcoder said, hash the third array, then the searching will be
O(1)
==> O(n^2 * lgn) or O(n^2) |
|
l*****e
发帖数: 1374 | 31 其实就是Dynamic order statistics
大家可以参考算法导论14.1内容:
需要在O(lgn)时间内取得第i大元素，同时调整树的时间也应该在O(lgn) |
|
a********m
发帖数: 15480 | 32 背景：
5月底layoff。layoff那天请假和朋友出门挖贝壳了，没赶上开会。。。然后就开始了漫长的找工作（心理感觉）长征。知道消息一下就晕菜了。赶快查了h1b的规定还有写信问hr和律师公司的规定。律师真是忙，写邮件要几天才恢复，约后几天的半小时时间谈谈，结果错过了两次。。。干脆不理it了，先转b2再说。
申请：
一些公司猎头闻风而来，公司hr也帮俺们这帮倒霉蛋群发申请工作邮件，开始还是感觉良好的。折了几个电面和programming test以后走向另外一个极端。。。主要就是还从打击中恢复，还没准备好面试就被突然袭击。其中有几个非常想去的公司都挂了，郁闷的要死。还好6月中混到2个onsite.开始集中精力准备onsite,也暂停发简历。
面试:
先说折掉的D. 飞德州晚点2小时，11点多才到旅馆，晚上，照常出门逛一下，看看热闹，自己安慰自己是熟悉环境，实际是不喜欢看书。。。话说austin真热。。。下午走的时候是108度。。面试非常顺利。题目难度一般。真正算法也就是A*寻路算法。其他都是实际应用中的问题。还有点到直线距离一类的几何问题。总的来说游戏行业对算法要求不高，有实际经验再准... 阅读全帖 |
|
b*******y
发帖数: 2048 | 33 强贴前排就座
了漫长的找工作（心理感觉）长征。知道消息一下就晕菜了。赶快查了h1b的规定还有
写信问hr和律师公司的规定。律师真是忙，写邮件要几天才恢复，约后几天的半小时时
间谈谈，结果错过了两次。。。干脆不理it了，先转b2再说。
觉良好的。折了几个电面和programming test以后走向另外一个极端。。。主要就是还
从打击中恢复，还没准备好面试就被突然袭击。其中有几个非常想去的公司都挂了，郁
闷的要死。还好6月中混到2个onsite.开始集中精力准备onsite,也暂停发简历。
闹，自己安慰自己是熟悉环境，实际是不喜欢看书。。。话说austin真热。。。下午走
的时候是108度。。面试非常顺利。题目难度一般。真正算法也就是A*寻路算法。其他
都是实际应用中的问题。还有点到直线距离一类的几何问题。总的来说游戏行业对算法
要求不高，有实际经验再准备下都不太难。后来挂的地方是午饭时间一个俗到不能再俗
的问题。。。你的弱点是什么。。。俺找了一个n年前年轻时候的不好的习惯，然后强
调这n年都在不断注意和改进。。。结果it只听了前半: 句。另外一个是complishment
。本着谦虚... 阅读全帖 |
|
P**********c
发帖数: 3417 | 34 赞。
了漫长的找工作（心理感觉）长征。知道消息一下就晕菜了。赶快查了h1b的规定还有
写信问hr和律师公司的规定。律师真是忙，写邮件要几天才恢复，约后几天的半小时时
间谈谈，结果错过了两次。。。干脆不理it了，先转b2再说。
觉良好的。折了几个电面和programming test以后走向另外一个极端。。。主要就是还
从打击中恢复，还没准备好面试就被突然袭击。其中有几个非常想去的公司都挂了，郁
闷的要死。还好6月中混到2个onsite.开始集中精力准备onsite,也暂停发简历。
闹，自己安慰自己是熟悉环境，实际是不喜欢看书。。。话说austin真热。。。下午走
的时候是108度。。面试非常顺利。题目难度一般。真正算法也就是A*寻路算法。其他
都是实际应用中的问题。还有点到直线距离一类的几何问题。总的来说游戏行业对算法
要求不高，有实际经验再准备下都不太难。后来挂的地方是午饭时间一个俗到不能再俗
的问题。。。你的弱点是什么。。。俺找了一个n年前年轻时候的不好的习惯，然后强
调这n年都在不断注意和改进。。。结果it只听了前半: 句。另外一个是complishment
。本着谦虚的态度。... 阅读全帖 |
|
k****n
发帖数: 369 | 35 来自主题: JobHunting版 - 一道G老题 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 ... 阅读全帖 |
|
f****4
发帖数: 1359 | 36 修改了一下try_find_kth函数，新的函数可以同时handle O(lgn+lgm)和O(lgk)的情况
bool try_find_kth(int a[], int lowa, int higha, int b[], int lowb, int highb
, int k)
{
while(lowa<=higha)
{
int mid=lowa+(higha-lowa)/2;
if (mid>=k)
{
higha=mid-1;
continue;
}
if(a[mid]b[k-mid-2]))
{
printf("find %dth %d\n",k,a[mid]);
return true;
}
else
if(a[mid]>b[k-mid-1])
higha= mid-1;
else // a[mid>b[k-mid-2]]]
lo... 阅读全帖 |
|
i*******h
发帖数: 216 | 37 I feel that a sort is necessary, so at least O(NlgN). After that, a brutal
force can solve it in O((N**2)*lgN). Can remove the lgN if hash table is
used.
Simply put, for each element Ai, for each element Aj after Ai, get their
delta, and then check if Aj+delta is in.
Maybe DP is better? |
|
O******i
发帖数: 269 | 38 利用从根开始这个特殊要求，把current_sum作为参数传下去，是可以达到O(N)
不过考虑到PrintPath是O(lgN), 则如果要打印path的话，总体复杂度是否还是要O(N*
lgN)？ |
|
H***e
发帖数: 476 | 39 来自主题: JobHunting版 - 问个算法题 假设N用二进制表示为 1101 ， 一共有m 位,ie 4，
可以考虑一个虚拟的二进制树，不用建树，所以不会增加复杂度
因为这个树一定是binary的，并且是 complete tree（ heap 的那种结构 ，只有最后
的leaf可能有gap)
定义full tree为完树，也就是总共有2^n + 1的那种
先算一下所有以0为root的full tree的中1的个数，
f(k) = 2f(k-1) + 1 and f(2) = 1 f(1) =0
比如: full tree:
0
0 1
0 1 0 1
f(3) = 3
接着， 对N的二进制(1100)表示进行处理，从最高位开始，如果是0什么都不做，进入
下一位， 如果是1，则以为着有一个full tree的以0为root的存在，在sum = sum + f(
4) + 1 (此位) ，然后进入下一位。
这里为1，意味着有0为root的full tree存在 sum=sum+f(3)+1
再下一位0,什么都不做，进入下... 阅读全帖 |
|
A****e
发帖数: 310 | 40 证明是对的.redcrab的程序我是这么理解的，里面有这么一段
// we need to find the range of the TowSums that have the same value.
所以如果把所有same value的这些都找出来，复杂度就变成了O(N)，而不是O(lgN^2)=O
(lgN).总的复杂度就变成了O(N^3). |
|
c****m
发帖数: 11 | 41 re，感觉给任意一个节点找前驱和后继都是lgN的操作啊，感觉应该lgN * m的复杂度 |
|
l*********8
发帖数: 4642 | 42 考虑一个比杨氏矩阵弱的情况A： 只要求矩阵每行有序，不要求每列也有序。
in-place 调整一个矩阵来满足条件A，可对每一行做quick-sort。
每一行时间是O(n*lgn), 有m行，所以总时间复杂度是O(m*n*lgn).
所以，我认为，对于要求更高的杨氏矩阵，不可能在O(m*n)time in-place调整完成。 |
|
k****r
发帖数: 807 | 43 lz, 关于sort的特点，ls说的都很好了。
对于你的困惑about lgn space of quicksort，我个人认为是quicksort没层递归需要
为stack存下partition point，这样一层一层的，需要lgn space。
我自己的理解，不知道对不对。 |
|
p*******f
发帖数: 15 | 44 一共两次电面 （没让签保密协议）
一面：1. Fabonacci number，给了三种解法，最快lgn
2. 从1加到100，不让用循环，不让用递归
二面：排好序的矩阵，从左到右升序，从上到下升序，要求判断给定的元素是否在矩阵
里，给了三种解法，最快lgn （跟面试官说了可以用master定理，但是忘了细节）
两次面试都完成了题目，做了boundary check和test cases
电面结果：被拒。
号外：本人已有工作（OPT），在linkedin上被recruiter联系，因为听说了“天价
offer”，就投了。因为当时比较忙，就跟recruiter把面试推到半个月后，recruiter
后来没有联系我。我打电话过去，被告知如果学位不是未来三个月之内拿到，就不能面
试。
可是不到一周，对方打电话过来问我第二天能不能面试。之后两次面试，自我感觉不错
，没有出现重大失误，按以往经历，GF之类的公司都会给onsite，结果被W告知被拒。
两次面试官都是老印，我都礼貌代之，据说也都给我了正面评价（第二个口音太重，很
多地方让重复了几遍，不知道是否这个有影响）。recruiter说tea... 阅读全帖 |
|
l*****a
发帖数: 559 | 45 第二题leetcode上只给出了nlgn的解法。lgn的解法是如何得到的？
第一题有lgn的解法，不过嫌复杂被放弃掉了。 |
|
c********t
发帖数: 5706 | 46 明白了，多谢！
把你说的扩展为n,要开至少n空间，存所有path，（用map好些）divide and conquer,
（如果每次不释放被conquer的数的path的话，还需要更多空间）最后留下最大数，和
它的path，这时候的path应该是lgn的。理论上比较次数为 n+lgn-1，但是存储读写次
数增加很多，时间优化了吗？ |
|
y****n
发帖数: 743 | 47 改编成整数开方。算法复杂度说不清楚，远好于O(lgN)。
我只假设是O(lg(lgN))。
static Int64 SqrtInt(Int64 num)
{
Int64 maxRoot = (Int64)1 << 31;
Int64 root = 1;
Int64 oldDiff = Int64.MaxValue;
Int64 diff = num - root * root;
int loop = 0;
while ((loop < 2) || (Math.Abs((double)diff) < Math.Abs((double)oldDiff)
))
{
root = Math.Min(maxRoot, root + diff / root / 2);
oldDiff = diff;
diff = num - root * root;
loop++;
}
return (diff < 0) ? root - 1 : root;
} |
|
s****9
发帖数: 22 | 48 我错了 应该是 lgn + lgn/2 + lg n/4 .. |
|
c******a
发帖数: 789 | 49 来自主题: JobHunting版 - 问到G家题 我不明白了，in-order怎么都要从最小node开始，一个个按顺序走到最后的。相当于一
个array去遍历，怎么lgN啊？
严密一点一个balanced BST，楼主解法我还是觉得是lgN。 |
|
r*******e
发帖数: 7583 | 50 二分递归，大的三角形等于矩形加两个小三角形
+
+ +
+++++
+ | +
+ | +
++++++++++
令 mid = (n - 1)/2
f(n) = sum(0...n-1) = sum(0...mid) + sum(mid...n-1)
= h(mid)*mid + 2*f(n/2)
其中h(mid)的计算可以用binary search，O(lgn)
所以f(n) = 2*f(n/2) + O(lgn)
根据master's theorem, f(n)复杂度是O(n)
in |
|
