f*****w
发帖数: 2602 | 1 精华区里面的问题 矩阵行和列都排好了 需要按顺序打印出所有元素
1 2 3
4 5 6
7 8 9
讨论的人说用heap 但是用heap无非也要n^2lgn；
而把整个matrix认作一个数组排序其实也就n^2lgn^2 = O(n^2lgn)
还有更好的办法么？ |
|
a*u
发帖数: 97 | 2 给一个string建立suffix array，然后sort这些substrings，复杂度是多少？O(nlgn)
or O(n^2lgn)?
比如 String "bananna", size n = 7
suffix array
{
banana
anana
nana
ana
na
a
}
after sorting
{
a
ana
anana
banana
na
nana
}
for a string size n, creating the suffix array is O(n), sorting is supposed
to be O(nlgn), but I somehow feel it is O(n^2lgn), since the comparison
between two substrings are O(n).
Where did I miss? |
|
a*u
发帖数: 97 | 3 又查了下，brute force就是n^2lgn, 但是现在有improved O（nlgn）算法，也有exact
bound n的算法了。恩
) |
|
r****o
发帖数: 1950 | 4 那复杂度是O(n^2lgn). 这题是不是不能用hash? |
|
r****o
发帖数: 1950 | 5 大家看看我的想法对不?
可以模仿merge sort,先考虑N为偶数的情况
设这N列为c1,c2,...,cN
将c1和c2, c3和c4, ..., c_{N-1}和cN 两两 merge成一个长2N的列，设为d1,d2,...d_{N/2}
然后再将d1和d2,d3和d4,...,d{N/2-1}和d{N/2}两两merge成一个长4N的列，
如此反复merge,直到最后剩下两个长N*N/2的列，用binary search可找到median。
时间复杂度，O(N)+O(2N)+...+O(N*N/2)+O(2lgN)=O(N^2 lgN).
空间复杂度O(N^2).
当N为奇数时，可将最中间那列先空着，当左右两边都merge成了长(N-1)N/2的列后，再merge成一个长(N-1)N的大列，然后问题可归结为一个长(N-1)N的列和一个长N的列，都排好序，找median的问题。
时间复杂度和空间复杂度应该和偶数时一样。 |
|
f*****w
发帖数: 2602 | 6 能不能请教下为什么两个loop能搞定？
我觉得如果没有额外空间的话只能做到O(N^2lgN)阿 |
|
f****4
发帖数: 1359 | 7 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... 阅读全帖 |
|
n****r
发帖数: 10 | 8
嗯，就是这样的，相对于trie会更节省空间，时间复杂度为O(n^2lgn). |
|
j*****h
发帖数: 62 | 9 Programming pearls里好像是提到过这个问题，没记错的化，它是用suffix array
来作的。算法很简单，假设string长度为n,以‘\0'结尾。开辟一个字符指针数组长度
为n，每个指针依次指向string的一个suffix。把该数组看成n个字符串的数组，排序。
再scan一遍，找相邻两个字符串最长的common prefix，即可。复杂度O(n^2lgn).
这种算法是允许overlap的，也就是说'ANA'是BANANA的最长重复子串。
AN
repeated |
|
e***r
发帖数: 68 | 10 资料说红黑树的高度最高不超过2lgN. 想知道这个系数"2"是怎么来的。
最好能给出一个输入串，生成的红黑树，高度为2logN的。谢谢了！ |
|
n*******r
发帖数: 444 | 11 Divide & Conquer应该可以解决这个问题．把矩阵一分为二，递归地解决每一个
sub-matrix, 再考虑across sub-matrix border的方案，这应该是一个
O(N^2lgN)的算法．
另外一个方法是对每一个black cell分类，即：可以为lowerLeft, upperRight,
lowerRight and upperLeft的cell,然后对他们做配对处理，（可以考虑把它
转成图的问题，即求有向图最大的circle). |
|
