p*****a
发帖数: 147 | 1 这题正解是什么？
- 树结构，O(lgn), how to build tree? 怎么用二分加速？
- 矢量乘法？
- scan all polys, find the min poly that contains the given poly. O(n), easy
to understand and divide to multiple machines.
10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，
要么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求
出最小的包含它的多边形。已知有现成的函数可以判断两个多边形是否相互包含，
iscontained(poly p1, poly p2)。
如何加速？如果在多机的情况下呢？
=> 可以用树结构表示包含的关系。
可以用二分搜索做加速。
多机的话可以range一个机器处理一个区域，另外要考虑前端处理机的负载不要成为瓶
颈，所以让每个机器自己判断此多边形是否包含。 |
|
i**9
发帖数: 351 | 2 This question is a bit different with the one on careercup, careercup 上那道
题是search a key,跟这个（只要求找出去拐点,）不一样, so it is doable in O(
lgn) for repeats |
|
|
g*********s
发帖数: 1782 | 4 btw, i think the complexity O(lgN) requires the bst balanced. |
|
g***s
发帖数: 3811 | 5 他的解法通用啊。哪种理解都可以。
主要是sum(x)递增,sum(x,n)递减。所以sum(x) - sum(x+s-n)单调递增。再O(n)求得
sum(i)以
后，O(lgn)二分可以找到最小的x。
case 1: s=1的时候，就是所有都乘以距离（当前×0）
case 2: s=3就是当前×1，其它乘以距离。
如果当前的×1，距离邻居×2，这个跟所有乘以距离(case 1)等效。
case 1，当pipe=1的时候，就是weighed median. |
|
k*******p
发帖数: 219 | 6 fib计算有lgn的解法，按照这样的计算，自然不需要o （n） |
|
g**e
发帖数: 6127 | 7 this is O(n^2*lgn). there is o(n^2) algorithm.
use head and tail pointers in your second loop to do the search. |
|
m**q
发帖数: 189 | 8 恩，最近刚看过interval tree，这个应该是对的。
复杂度是O(max(k, lgn)), k为和i有overlap的
节点数 |
|
g**u
发帖数: 583 | 9
这个应该是可行的，但是我不确定是
max（k, lgn)
如果是ordinary BST的话，怎样返回下一个overlap的区间呢？
就是说寻找overlap的不是O(k)， 是O(k*log n)么? |
|
m**q
发帖数: 189 | 10 CLRS, 2nd
12.2-8 是可以证明的
实际上就是连续调用successor直到当前
node和给定的range没有overlap，假设
调用successor次数为k，则复杂度是O(k+lgn) |
|
m**q
发帖数: 189 | 11 假设每个任务开始结束为start[i], end[i],对应的权值为a[i],
先把数组按start[i]排序，设从i...n的工作中，总的最大权值为f[i],则：
f[i] = max { f[i+1], a[i] + f[k]: k是i之后和i不冲突的第一个元素 }
排序O(nlgn),遍历a[]数组O（n),对每个元素i用二分法找对应的k，O(lgn),
总复杂度为O(nlgn)。
这个方法对不？
O( |
|
|
g****v
发帖数: 971 | 13 最优算法是n+lgn-2. CLR书上的一个课后题。 |
|
p*****a
发帖数: 147 | 14 来自主题: JobHunting版 - G家一道题 这题正解是什么？
- 树结构，O(lgn), how to build tree? 怎么用二分加速？
- 矢量乘法？
- scan all polys, find the min poly that contains the given poly. O(n), easy
to understand and divide to multiple machines.
原题见：http://www.mitbbs.com/article_t/JobHunting/31828487.html
10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，
要么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求
出最小的包含它的多边形。已知有现成的函数可以判断两个多边形是否相互包含，
iscontained(poly p1, poly p2)。
如何加速？如果在多机的情况下呢？
=> 可以用树结构表示包含的关系。
可以用二分搜索做加速。
多机的话可以range一个机器处理一个... 阅读全帖 |
|
a********m
发帖数: 15480 | 15 从头往后扫描。每个数字是当前可用数字从小到大排序的序号。 查找数字的部分可以
把所有数字做成一个bst. 叶结点是实际数字，其他结点是从这里往下的数字数目。 这
样查找数字是lgn. 每次去掉一个数字的时候更新路上的结点值。 |
|
a********m
发帖数: 15480 | 16 前面那个树开始是这样的，前面两行是计数，最后一行叶子是实际数字：
。。。。4
。。。2。。2
。。1。2。3。4
取走第一个4以后是
。。。。3
。。。2。。1
。。1。2。3
再取走1是
。。。。2
。。。1。。。1
。。。。2。3
关键是查现在的第几个数字需要lgn复杂度。所以很自然用树表示。 |
|
a********m
发帖数: 15480 | 17 original index不用,用了反而不能lgn了,因为你需要更新it. 只用左子树叶子数目应
该可以。 |
|
|
j**l
发帖数: 2911 | 19 可以化归为这样一道题：
设计一个有序的数据结构，最初里头有自然数1到n这n个元素，
随后这些元素可以被删除，但剩下元素仍然保持有序。
要求实现方法GetKthElement(int k)和RemoveKthElemenet(int k)，使得它们在任意时
刻都不超过O(lgN), N为当前的元素个数, 1 <= k <= N
感觉要结合BST之类 |
|
k****n
发帖数: 369 | 20 There is a straightforward solution:
Suppose we have a set of 1 to n, then from the 1st element of the count-
array c[], a[i] is the c[i]'th element left in the set, when we move forward
, we also need to delete a[i] from the set.
So the problem is, how to find and delete k'th element in lgn time.
This is traditional. A BST with subtree size should be enough. |
|
k****n
发帖数: 369 | 21 wrong, in a sorted vector, it is true that find k can be achieved in O(lgn),
but remove it need O(n). |
|
g***o
发帖数: 4 | 22
Use skip list can get lgn too. |
|
s*****y
发帖数: 897 | 23 我想过用skip list，skip list是排好序的，search element是lgn，但是要得到排第
几的element似乎不行。 |
|
g***o
发帖数: 4 | 24 Follow the solution from gloomyturkey. Build the skip list of 1~n. Every
time, simply fetch the number at the position of count array[i] and delete
it from the list, which is lgn time. |
|
P**********c
发帖数: 3417 | 25 map不是hashmap啊。map的插入和查找都是O(lgn). 就算插入查找都是O(1)，你这个也不是O(n), 这个要看map access
不存在的key的behavior。这种情况下它会插入一个新的key的，插入一个key么至少就是O(1)。所以你在不停的判断
m[a+1]的时候，map的size最终会涨到这组数的range, 同时时间复杂度也涨到O(range)了. hash_map有同样的问题。
hash_map也是从最底层实现起来的，它不是一个magical的只存n个数就可以O(n) access m(m>>n)个值的工具。 |
|
P**********c
发帖数: 3417 | 26 map不是hashmap啊。map的插入和查找都是O(lgn). 就算插入查找都是O(1)，你这个也不是O(n), 这个要看map access
不存在的key的behavior。这种情况下它会插入一个新的key的，插入一个key么至少就是O(1)。所以你在不停的判断
m[a+1]的时候，map的size最终会涨到这组数的range, 同时时间复杂度也涨到O(range)了. hash_map有同样的问题。
hash_map也是从最底层实现起来的，它不是一个magical的只存n个数就可以O(n) access m(m>>n)个值的工具。 |
|
g*****i
发帖数: 2162 | 27 用2分法可以达到O(lgN+lnM),很多情况下比o(k)快
O( |
|
P**********c
发帖数: 3417 | 28 题目要求是O(k)啊。O(lgn+lgm)是跟那个找median的算法类似吗？ |
|
|
f****4
发帖数: 1359 | 30 0 1 2 3 4 5 6 <- index
1 3 5 7 9 11 13
2 4 6 8
找第四大的数k，k只可能在7 9 11 13和 2 4 6 8中间
先处理a[3~6]7 9 11 13
low a[3] 如果 7是k，那么必有 a[3] > b[3]，不然说明当前数7小于k
high a[6] 如果13是k，那么必有 a[6] > b[0]，不然说明当前数13大于k
当low < k && high > k的时候，我们用2分查找，看mid(9)
mid a[4] 如果 9是k，那么必有 a[4] < b[3] && a[4] > b[2]，
如果a[4] > b[3] a[4]大于k
如果a[4] < b[2] a[4]小于k
这里，我们用mid 替换 high, k只能在[3~4]中间，第一个数组查找结束，k不在第一个
数组里面
那么k必然在b[0~4]里面
low b[0] 如果2是k，必有b[0] > a[6],不然说明当前数2小于k
high b[3] 如果8是k，必有b[3] > a[3],找到
这里需要根据当前a[] index... 阅读全帖 |
|
m**q
发帖数: 189 | 31 我的思路和你类似，不过我觉得每取完一个元素后要把这个元素排除，
这样才能保证第i个被选择概率和score(i)成比例
最简单的实现是每次把取过的元素swap到数组前面，复杂度应该是O(kn)
一个可能的优化的方法是组织成一个顺序统计树，每个节点不是存它的子树的
子节点数，而是存它的子树的score的和，这样每次生成随机数可以用
O(lgn)找到对应节点，选k个数复杂度为O(klgn)。生成树应该需要O(nlgn)。
总复杂度O(nlgn)，如果k是O(n)的话这个方法更优
求指正
是( |
|
m**q
发帖数: 189 | 32 这个思路我当场肯定想不到...
不过想了想，所有小矩形最多可能有O(n^2)个，
对它们进行排序需要O(n^2*lgn)
如果用sweepling line algorithm，用一个set记录
过程中的端点，应该可以O(nlgn) |
|
m**q
发帖数: 189 | 33 思路大概是这样的
因为所有矩形的底边都在x轴上，把每个矩形的左上角和右上角的坐标记录到
一个数组中，每个元素是 pair, int start>，每个矩形
在数组中有两个元素，代表左右两条边，start为1表示开始，为0表示结束。
比如，一个矩形的x轴开始坐标为x1，结束坐标为x2，高为y，则在数组中它
对应的两个元素是 <, 1>, <, 0>
可知n个矩阵生成的数组中有2n个元素，然后sort数组，复杂度O(nlgn)
然后用sweepling line algorithm，扫描数组，用一个BST记录当前
overlapping的所有矩形。
遇到矩形的左边时(start==1)，判断边的高度（即当前y值）是否大于BST中
的最大高度，大于则记录两个点，（当前x值，BST中最大高度），
(当前x值，当前y值)。把当前y值放入BST
遇到矩形的右边时(start==0),把当前y值从BST中删除，如果BST有相同值只删除
一个。判断边的高度（即当前y值）是否大于当前BST中的最大高度，大于则
记录两个点，（当前x值，当前y值... 阅读全帖 |
|
a*********0
发帖数: 2727 | 34 来自主题: JobHunting版 - 一道G家题 Find or determine non existence of a number in a sorted list of N numbers
where the numbers range over M, M >> N. require O(lgn) |
|
a********m
发帖数: 15480 | 35 来自主题: JobHunting版 - 一道G家题 linked list不可能有lgn. |
|
a*********0
发帖数: 2727 | 36 来自主题: JobHunting版 - 一道G家题 给一个有序的M到M+N的序列，找不在这个序列中的数。要去lgn |
|
i**********e
发帖数: 1145 | 37 来自主题: JobHunting版 - 一道G家题 这题到底是一个还是两个序列？
发信人: absolute100 (绝对100度), 信区: JobHunting
标 题: Re: 一道G家题
发信站: BBS 未名空间站 (Thu Jul 21 18:38:53 2011, 美东)
给一个有序的M到M+N的序列，找不在这个序列中的数。要去lgn |
|
h**********8
发帖数: 267 | 38 hash_map: O(1)
map: O(lgn) RB-Tree |
|
k****n
发帖数: 369 | 39 来自主题: JobHunting版 - 一道G老题 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 ma... 阅读全帖 |
|
k*j
发帖数: 153 | 40 对。不好意思，我那是笔误，O(nlgn)都错写成了O(lgn)
谢谢。我才意识到merge k个array需要一个heap(size k)来找当前最小值，所以每一步都需要lg(k)时间。总共是nk个元
素，nkO(lgk) |
|
P**********c
发帖数: 3417 | 41 insert过程中，保证两个heap一样大，或者max heap多一。max heap里的所有值小于min heap里的所有值。每次insert只需要比较要insert的数跟两个heap的root决定进哪个heap, 如果insert后两个heap大小不满足要求则把其中一个的root插到另一个。 insert复杂度O(lgn).
找median时，如果两个heap一样大，则median为两个root的平均。
如果max heap多一，则为max heap的root
找median操作为O(1). |
|
s*********e
发帖数: 197 | 42 我觉得heapify一次是O(lgn). bottom up min-heapify应该是O(n). |
|
m**q
发帖数: 189 | 43 Right t is no more than O(lgn)
But we still need to walk through all these
(k1+1)(k2+1)...(kt+1) numbers, so seems the complexity
for this is not going to be O(nlgn) with this method... |
|
f****4
发帖数: 1359 | 44 k
最坏的情况： n=m，k=n^2，你的方法是O(n^2*lgn)
我问的是有没有O(n)的解法。
有人说能转换成杨矩，有点不明白：对一个满的n*m杨矩，有O(n)的解法找到第k大数么？ |
|
f****4
发帖数: 1359 | 45 k
最坏的情况： n=m，k=n^2，你的方法是O(n^2*lgn)
我问的是有没有O(n)的解法。
有人说能转换成杨矩，有点不明白：对一个满的n*m杨矩，有O(n)的解法找到第k大数么？ |
|
q****x
发帖数: 7404 | 46 O(n)。应该可以O(lgn)吧？利用位操作。 |
|
b***e
发帖数: 383 | 47 这里说用 O(lgN)的空间并不是指交换位置或者做partition时所需要的空间，而是指在不
断递归时保存递归点（i.e., start point, end point）所需要的空间。 |
|
a********m
发帖数: 15480 | 48 这样你至少有（n^2）/2个元素要处理，就算每次处理是o(1)也要o(n^2)，你的（lgn）
咋出来的？ |
|
z****u
发帖数: 104 | 49 感觉和 LRU 很像，不过 LRU 是记录每个元素出现的先后，这个是元素出现的次数
用 hash + heap
hash 用来 O(1) access 对应的地址；按照出现次数来维护 heap。
每次 push 和 pop 的时候需要对他在 heap 中的 node 做up-heapify 或 down-
heapify，心元素的话就是 heap 的 insert，最坏情况都是 O(lgn)
top 是 O(1)
functions |
|
r*******h
发帖数: 315 | 50 你没有理解min heap和max heap的特点,而且建堆也是要时间的，用max heap，保持heap大小为
k，利用删除堆最大元素只要lgn的特点，所以找第k小只要nlogk，如果你用min heap同样的做法，
最后留下的是最大的k个数，或者你得借助min heap来一次排序，那就跟quick sort一样
最后要nlogn. |
|
