h*********i
发帖数: 116 | 1 好像不用求lcs lcs怎么也得用到dp把，那样就不是线形了。 |
|
r********7
发帖数: 42 | 2 这个会不会有问题，比方说X=[3,2,1,0,1,2]
线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
但正确结果因该是[0,1,2] |
|
h*********i
发帖数: 116 | 3 对需要一些改进
如果结果只有一个元素
可以线形扫描看整个序列是不是单调减，如果是自然单调升就是一个元素
如果不是就把违反单调减的那两个元素拿出来
作为初始的字序列的前两项就好了
。。。。。。。。。就是一个单调升
这样也是合乎题意的，不过感觉这样做就没什么意思了。
我觉得如果问最长单调升子序列查找更有意义，是不是
应该是最长单调升序列查找阿。 |
|
|
g*******y
发帖数: 1930 | 5 你只维护一个数组，肯定是不对的
eg，4 5 6 1 2 3 4
f |
|
p*********a
发帖数: 21 | 6 一般来LIS只需要求出长度, 这个方法足够了, 我强调了d的结果并不是最后要求的LIS. |
|
s****i
发帖数: 150 | 7 不可以sort吧。假设4,5,6,1,2,3，最长子列是4,5,6或者1,2,3，你sort了之后不就变
成1,2,3,4,5,6了。。。
这个用DP好了 |
|
j*********h
发帖数: 21 | 8 no.
in step3 , all elements have already been sorted.
for example,
[3,2,1,0,1,2]->[0,1,1,2,2,3]
actually, if I write out each element in the format (value, position), the
above will become
[(3,1),(2,2) ,(1,3),(0,4),(1,5),(2,6)]->[(0,4),(1,3),(1,5),(2,2) ,(2,6),(3,1
)].
in the resulting array, when scanning, you will get (0,4) first, put it in
resulting queue 1.
then you get (1,3), since (3<4),you will dump (0,4), put (1,3) in queue 1
then you get (1,5), keep it in queue1.. since 5>3
then you |
|
j*********h
发帖数: 21 | 9 the reason not to dump (2,2) is that we already have 2 elements in queue2,
in this case, if you dump 2 elements in exchange for 1 element, it would be
worse.
the
,1
in |
|
z********y
发帖数: 109 | 10 public static int MCSS(int [] a) {
int max = 0, sum = 0, start = 0, end = 0, i=0;
// Cycle through all possible end indexes.
for (j = 0; j < a.length; j++) {
sum += a[j]; // No need to re-add all values.
if (sum > max) {
max = sum;
start = i; // Although method doesn't return these
end = j; // they can be computed.
}
else if (sum < 0) {
i = j+1; // Only possible MCSSs start with an index >j.
s |
|
|
|
z********y
发帖数: 109 | 13 haha
看错了。这个可以用suffix tree做吧 |
|
|
R***r
发帖数: 120 | 15 无意中看到这道题，google了一下竟然发现很多提问但没一个可靠的答案，大家帮忙看
看。
Given two arrays of numbers, find if each of the two arrays have the same
set of integers? Suggest an algo which can run faster than NlogN without
extra space? |
|
f*********r
发帖数: 68 | 16 典型的DP, 至少有3,4种方法可以解决. 不过基本上都是从以下状态方程来的
dp(i,j)=min{max{dp(i-1,k-1),dp(i,j-k)}+1, 1<=k<=j}
直接搞是时间O(N^3)空间O(N)的. 考虑二分可以降到时间O(N^2logN)空间O(N), 用上DP
的四边型不等式可以进一步到O(NlogN)+O(N), 不过最好的方法是时间O(N), 空间O(
logN)的
有<
, |
|
b***e
发帖数: 269 | 17 能不能解释一下这个状态方程？谢谢！
典型的DP, 至少有3,4种方法可以解决. 不过基本上都是从以下状态方程来的
dp(i,j)=min{max{dp(i-1,k-1),dp(i,j-k)}+1, 1<=k<=j}
直接搞是时间O(N^3)空间O(N)的. 考虑二分可以降到时间O(N^2logN)空间O(N), 用上DP
的四边型不等式可以进一步到O(NlogN)+O(N), 不过最好的方法是时间O(N), 空间O(
logN)的
有<
, |
|
f*********r
发帖数: 68 | 18 这个状态方程的优化到极限是(NlogN)的, 如果你想更好的方法, 从状态方程下手, 可
以到O(N) |
|
a*****e
发帖数: 51 | 19 来自主题: JobHunting版 - 一道面试题 (1) Sorting, time: O(nlogn), space: O(1)
(2) Hashing, time: O(n), space: O(n)
(3) Bitwise operation, How can you use XOR, since after XORing every
elements, both those elements which occur 1 time and the one occurring 3
times will be left indistinguishable? |
|
g*******y
发帖数: 1930 | 20 好像是对的
挺好的方法啊，这么说来只要这个subset的元素个数是常数，都统一是nlogn的复杂度
不愧是传说中的牛人~
a
that |
|
m*****f
发帖数: 1243 | 21 我详细说说吧， 就是closest pair的思路
1. 在x轴上排序
2. 取中点x_middle把点分成左半边和右半边
3. 递归寻找左半边和右半边距离小于k得pair
4. 同时还有一边在左，一边在右的pair,
5. 3+4 = all answer
其他都是O(nlogn)没问题， 第四步如果强解一样是o(n^2), 但是因为有条件是小于k,
那么只要考虑 x > x_middle-k 的左边点和 x < x_middle +k 的右边点即可，
并且对某个x_left, 只需考虑
x_middle < x_right < x_middle + k - (x_middle-x_left)
的右边点， 可知是O(n).
应该没错把 |
|
g*******y
发帖数: 1930 | 22 分冶可以做到O(nlogn)
对left right半截分别解决子问题，然后得到:
{neg_left},{pos_left} | {neg_right},{pos_right}
再把{pos_left}跟{neg_right}调换位置就行了(就是个简单的数组rotate) |
|
k*k
发帖数: 49 | 23 @geniusxsy:
这个算法是 nlogn 吗？
1) while(k log N
2) for(int i=2; i<=k;i=i<<1) ==> log K
3) for(int j=0;j N/i == N/log K
4) the content of the inner most loop seems to me has N complexity worst
case.
so seems to me 2)*3)*4) already N^2
很可能是我哪里没搞明白。。。
先谢谢了。
int k = 1;
while(k
for(int i=2; i<=k;i=i<<1){ //k是刚刚大于等于N的某个2的整次方数
for(int j=0;j
int pos1 = j, pos2 = j+i/2;
if(pos2>=N) continue;
//找当前这段，左半边第一个正数
while(arr[pos1]<0 && pos1
//找当前这段，右半边第 |
|
g*******y
发帖数: 1930 | 24 怪mitbbs了，显示不了tab缩进，每行都变成左对齐了。。。呵呵
while(k)就是单独的一句话(单独的一个loop),跟下面两个for loops没关系。
while(k)的作用，只是要计算一个等于或者约大于N的2的整次方数。
其实我完全也可以把while(k)改写成：
k = 1 << (Log2(N-1)+1);
至于你说的2,3,4要O(N^2)是不对的，整个j loop做完，也就是O(N).
所以最后复杂度就是 log(k) * O(N) = O(NlogN)
这个本质上就是一个divide-conquer的非递归实现，复杂度当然不会有变化。 |
|
m*****f
发帖数: 1243 | 25 我也有类似的疑问, 前面是 nlogn 毫无疑问, 但是这里三个while, 先交换了
左边的正数和右边的负数, 然后再分别调换次序保证顺序正确, 这里能保证是
O(1)? |
|
w********p
发帖数: 948 | 26 类似qsort要用O(nlogn) space, merge sort要用O(n) space, 不合要求
有关array shift, rotate 的操作running time 是O(n), 也不合要求
用linked list O(n)running time 和 O(1) space
1, you have a linked list for {1，5， -5， -8，2， -1，15 }
2. remember the original linked list head, scan all note one by one, if
the
number is negative, remove it from the original liked list, and put it to
new linked list, you will get
1, 5, 2, 15
-5, -8, -1,
3. link the tail of second linked list to head of original linked list
-5, -8, -1, 1, 5, 2, 1 |
|
S**Y
发帖数: 136 | 27 faint..似乎确实是O(nlogn)
虽然里面有while循环，但是第二个for循环(using j)并没有遍历全部元素，而是跳跃的
，后面的while循环填补了跳跃的元素，刚好是O(n)... |
|
h*********i
发帖数: 2605 | 28 发现你刚才修改过了。
我也觉得O(NlogN)是最快的。
remaining matrix. |
|
c*****g
发帖数: 1137 | 29 easy to get n^2, not sure about nlogn |
|
m********0
发帖数: 2717 | 30 O(n^2) is trivial .
貌似前段时间Quant版讨论过，有人给出paper link
目前的最好算法就是 O(nlogn)。
记不太清楚了。 找了半天没找到。
up |
|
l***i
发帖数: 1309 | 31 wikipedia search 3SUM problem. There is no better solution than O(n^2)
currently and there are a number of problems that would have a faster
solution if 3SUM has a better than O(n^2) solution, say O(nlogn). |
|
g*******y
发帖数: 1930 | 32 速度只有靠多练习啊
你见过10分钟解难题并实现高效maxflow通过测试的牛人吗？人家那也是练了无数年的
功力啊
btw，我觉得这题就general case而言, nlogn就不错了吧？得sort一次吧？ |
|
f*********r
发帖数: 68 | 33 请教一下LCS怎么做到O(nlogn), 很容易么? |
|
m*****f
发帖数: 1243 | 34 hint 就是 "比如LIS现在是O(nlogn)了", 把LCS转换成LIS就可以了 |
|
m*****f
发帖数: 1243 | 35 LCS转换成LIS：
假设序列A, B, 首先纪录A元素在B中的位置(O(n)), 降序排列，然后按照元素顺序合并
为一个数组, 求此序列LIS (O(nlogn))
比如 A = {a, b, a, d, x, y, a}, B = {b, b, a, b, c, x, a}
a = {7, 3}, b = {4, 2, 1}, d = {}, x = {6}, y = {}
组成序列{7,3,4,2,1,7,3,6,7,3}
LIS 为 1 3 6 7, 即 b a x a |
|
r****o
发帖数: 1950 | 36 O(nlogn)的解法哪儿有？
这个好像有点难度。
array。 |
|
z*******y
发帖数: 578 | 37 用DP结合二叉搜索树可以实现
把已经扫描的元素存到二叉树里，二叉树的元素是<数组元素，到这个元素的LCS的长度>
这样在update到每个数组元素时候的LCS的时间就是logn，总的时间就是nlogn |
|
b*********n
发帖数: 1258 | 38 build prefix tree on dict. O(nlogn)
search on prefix tree for input string prefix, O(k^2)
k is the length of input string.
OR
hash dict prefix, O(h*n), h is word size in dict.
search input word prefix from hash table, O(k).
k is the length of input string. |
|
k***e
发帖数: 556 | 39 最简单的n^2，用类似radix tree？
即使nlogn好像也要借助suffix array，也不trivial
靠 谁考这个我当场和他拼了
血溅五步 哈哈
out |
|
g*******y
发帖数: 1930 | 40 把所有数写成二进制，然后把所有的数插入到一颗二叉树上成为leaf；定义左分支=0,
右分支=1，从root到每个leaf的路径的二进制编码等于leaf的数。
用两个指针p0, p1来“遍历”这个树，如果指针p0往左走，p1就尽可能往右走,vice
versa，思想是尽可能在高位(靠近root)选择两个相异的bit。
如果假设所有的数都是d位的话，复杂度就是O(nd),换句话说O(nlogn) |
|
g*******y
发帖数: 1930 | 41 我觉得如果要求连续，能找到nlogn的算法，再怎么进一步优化就没想到了。 |
|
g*******y
发帖数: 1930 | 42 Divide and conquer works? The "conqure" step takes O(n)? how?
我的想法是:
1. 转化为一个等价问题：
sum' = total sum - target_max_sum
问题转化为：在数组中找两段子数组，一段A数组从头开始，一段B数组在尾巴结束，这
两个数组之和>=sum'，这两个数组的元素个数之和最小
2. sumA[i]= a[0] + ... + a[i],
sumB[i] = total sum - sumA[i-1] ...
3. define一个map mA, mB; 然后：
mA.insert(make_pair(sumA[i] ,i+1));
mB.insert(make_pair(sumB[i] ,N-i));
这一步要O(nlogn), 因为map是要对key排序的。
4. 把map中的value值改变为:
mA[key] = min{k+1}, for all sum[k] >= key,
这一步只要O(n)，因为mA已经是按key排好序的;
现在这个mA中每一项的含义就是： |
|
g*******y
发帖数: 1930 | 43 如果题目要求子数组是可以不连续的subsequence，sort一遍从最小的开始求和就是一
个贪心解吧。
如果要求必须是连续的子数组，至少有nlogn的解(我前面贴的，我实现了一下，应该没
啥问题) |
|
g*******y
发帖数: 1930 | 44 1 2 3 4 5 6 7, M=3
指针从左往右走(循环的)
指针指到1的时候，count=1
指针指到2的时候，count=2
指针指到3的时候，count=3=M，所以第一个删除的数是3，然后count清零
指针指到4的时候，count=1
指针指到5的时候，count=2
指针指到6的时候，count=3=M，第二个删除的是6
指针指到7的时候，count=1
指针指到1的时候，count=2
指针指到2的时候，count=3=M，第三个删除的是2
指针指到4的时候，count=1
指针指到5的时候，count=2
指针指到7的时候，count=3=M，第四个删除的是7
。。。。。。
M
写个code出来，要求O(NlogN)
count |
|
g*******y
发帖数: 1930 | 45 达不到要求
题目说的是O(n)
而k是小于等于n的数
O(nlogk) = O(nlogn)
其实可以这样：
找到median后，对于每个数，算一个新的数组b[i] = abs(a[i]-median)
然后在b[i]中找k-th元素，然后再遍历一遍就可以找到k个最小的了。
这样保证是O(n)
这个题告诉我们，heap也不是万金油，呵呵 |
|
g*******y
发帖数: 1930 | 46 you mean O(N*N)?
But at least you can achieve O(NlogN) by first sort and then do some tricks. |
|
k*k
发帖数: 49 | 47 some thoughts...
build tree bottom up. nlogn tree construction.
(7) (3) (4) (1) (2) (6) (5) (8)
1) traverse:
merge adj element to produce
(7) (3,4) (1,2) (6,5) (8)
2) traverse again:
(7) (3,4,1,2) (6,5) (8)
3) traverse again
(7) (3,4,1,2,6,5) (8)
4) again
(7, 3, 4, 1, 2, 6, 5) (8)
5) again
(7, 3, 4, 1, 2, 6, 5, 8)
two adj. blocks merge if max(max(Block1), max(Block2)) - min(min(Block1), min(Block2)) == sizeof(block1 + block2) |
|
k*k
发帖数: 49 | 48 i think....
my "sol":
average case n log n, worst case n^2
just like constructing a binary search tree from a sequence of number
n log n average, n^2 worst... but we generally consider construction of a
binary search tree has complexity of nlogn |
|
h**k
发帖数: 3368 | 49
当然是建balanced binary tree了，那样worst case 就是O(nlogn) |
|
m*****f
发帖数: 1243 | 50 假设cell为x1,x2,x3,x4...
, ...
, ...
...
把这些pair基于第二个element排序, 每个整数出现了两次, 且在结果中相邻, 遍历结
果就可知哪些cell头尾相连
O(nlogn) time, O(n) space |
|
