z*******r
发帖数: 12 | 1 假设有m个list，每个list有n个数，同时假设每个list中没有重复的数字。
对于merge k sorted list那种方法来说，首先用priorityqueue merge，同时poll出来
数字时统计相同的数字有多少个。所以每个数字都要进队列一次，出队列一次，
priorityqueue中只能同时有m个数字。所以这部分时间复杂度是O(m*n*log(m))。
接着为了保证输出有序，对符合要求的数字排序，假设有x数字满足要求，时间复杂度
是O(xlog(x))
如果x不是很大，那么这种方法的时间复杂度应该是O(max(m*n*log(m), xlog(x))) ~ O
(m*n*log(m))
对于楼主方法来说，把所有数字放到HashMap中，时间复杂度是O(m*n)，再遍历一遍
HashMap挑出合法的数字，时间复杂度仍然不会超过O(m*n)
对于输出结果排序，时间复杂度是O(max(m*n, xlog(x))) ~ O(m*n)
对于最坏情况来说，每个数字都要输出，那么x=m*n，时间复杂度是O(m*nlog(m*n))
从时间复杂度的角度来说楼主的方法应该是要优于mer... 阅读全帖 |
|
s****r
发帖数: 68 | 2 请问2 sum O(n)怎么做？我看到有些答案说先scan一遍，build map or hash map，
then query that map。但是这个
1. 如果用map，build map一般是二叉树把，nlog(n).
2. 如果hash map，worst case n^2。而且平均也可能大于O(n)。 |
|
s****r
发帖数: 68 | 3 这个不正确吧。对排序的map，build map is nlog(n), access is O(logn).
对hash map，更复杂。需要分析average and worst case。
一般面试，除非要求，尽量不用map这种现成的复杂结构吧：你把复杂性都隐藏在
library里了，有时算法设计意义不大了。 |
|
P**********2
发帖数: 77 | 4
the
这个第3步怎么融合能比nlog(n)更好？ |
|
s****r
发帖数: 68 | 5
I don't know a comparison sorting based algorithm better than nlog(n). But I
can show some idea to integrate efficient sorting with 2-sum together. The
idea is to embed 2-sum check in quick sorting method as following:
Say the array is [a1, a2, ..., an], and the sum is s.
1. Select one element, such as, a1, then get b1 = s - a1. Assume that a1 <
b1, and use a1, b1 to partition the array to three parts A11, A12, A13, so
that the element in the first part A11 is no more than a1, and the element
... 阅读全帖 |
|
发帖数: 1 | 6 I think 二分 O(Nlog(max-min)) is good enough |
|
H**********5
发帖数: 2012 | 7 这题没刷过面筋30分钟都不一定能搞出来二分的代码。
骚年还是刷面筋吧
: I think 二分 O(Nlog(max-min)) is good enough
|
|
v******s
发帖数: 144 | 8 在preprocess用O(nlog(n))把所有x,y (x < y) 都存起来不就行了。怎么会有这样的题 |
|
N*****N
发帖数: 1605 | 9 转载的就不模板了，呵呵。
好像很难。 O(N^2)还差不多；O(Nlog(N))也可能行；O(N)怎么搞？
algorithm |
|
N*****N
发帖数: 1605 | 10 Nlog(N)非常容易，呵呵。N高步出来 :( |
|
s**********y
发帖数: 8135 | 11 (转载，接上贴)下面来试着谈谈巴赫。Soprano有一天对我说，她想抽空打击一下我们
这些巴赫的
爱好者。听了以后，顿觉诚惶诚恐。考虑到Soprano的功力，便提前一直再暗地里
准备：一旦见到Soprano的大作，我该如何反驳。
有个卖D版古典CD的哥们认识很多音乐爱好者，包括我。他跟我说，他做过一个统
计，在喜欢巴赫音乐的人中，理工科毕业的爱好者的比例要远远多于学文科的。
而对于李斯特和瓦格纳，这个比例正好反过来。我是这么来理解这个统计现象的：
1. 中国教育只把学生分为文理两大类。
2. 他们爱好音乐的程度基本上是一致的。
3. 音乐爱好者缺钱的程度基本上也一致。
4. 他们找到我那个卖D版音乐的哥们几率是基本一致的。
5. 理科学生受自然科学训练多年，文科学生受社会科学训练多年
6. 自然科学侧重公式定律，即自然的秩序。社会科学侧重诗词小说，即人类的情感
7. 人类总是喜欢能引起自身共鸣的东西
所以，巴赫的音乐中有更多的秩序美。证毕。
就我个人而言，一开始并没有觉得巴赫的音乐如何。是维瓦尔第的“四季”推倒了我
爱好古典音乐的第一张多米诺骨牌。推己及人的想，也许很少人能一上来就喜欢... 阅读全帖 |
|
w****g
发帖数: 727 | 12 just saw this, have you figured it out?
I can give you a good upper bound,
like nlog n-n+O(log n) +1/2t^2 logn,
when t=1, use Stirling, then take derivative with t, sum with n and
integrate with t
depends how precise you need,
lower bound could be got by some classical result of Riemann zeta function
which I forgot the detail. |
|
a****i
发帖数: 10 | 13 yes, I think nlog's post is a good one, though his humor would be prone to be
thought as cynic. Hash is a crypto primitive, many protocols/schemes are based
on it. It's like the CPU to PC. Sure it doesn't mean all PCs are trashes
though many are :)
看
设
攻
是
给
,
HA1了,而且大牛们已经担心SHA1也保不了多少天了,必须去造新的hash函数.造个新hash函
而
打
方,造hash函数相当于造CPU,其他的文章(包括顶尖会议的),协议(包括成了标准的)相
攒机子,IBM攒的好一点,电子商场攒的差一点而已.现在突然有人举个例子说Intel的PIII(
SHA0)算这个除法会出错,P4(SHA1)虽然没例子但也保不准,而AMD呢(MD5)不仅出错,而 |
|
|
f*****r
发帖数: 229 | 15 You're right. With some
priority queue structure(such as, a max-heap), it is nlog(n).
Would you please give some intuition about how to design a O(n) algorithm? I'm
not an algorithm person, and just want to get some idea for this problem.
Thanks. |
|
|
l*s
发帖数: 783 | 17 NLog不是visual studio Addin吧 |
|
g*****g
发帖数: 34805 | 18 I don't think it makes much difference.
Collections.sort is a modified mergesort with guaranteed nlog(n) performance,
You can mix IO and sorting, but performance is equivalent.
|
|
c*****z
发帖数: 182 | 19 比如有道题，我至今仍未看懂，bin packing problem
用heap实现，可以在o（nlog（n））完成
看了答案也不明白为什么是对的 |
|
w***g
发帖数: 5958 | 20 看大家都不吱声，我来抛砖引玉。我其实没什么好的算法。我觉得就是需要O(nlog k)。
第三种情况可能有巧妙的办法，但是前两种情况没什么好说的：
k = 3: O(n), 好歹每个数都要看一遍吧。
k = n/2: O(nlogn)，因为k = n/2的复杂度和k = n其实是一样的，而排序n个数需要O(
nlogn)。
of
(a
for
algorithms. |
|
w**q
发帖数: 3 | 21 Implement an algorithm to sort a linked list. Why did you pick the method
you did? Now do it in O(n) time.
how to get O(n)???
The famous sort algorithms are all O(nlog(n))
thanks a lto! |
|
c*******d
发帖数: 255 | 22 这不就是这些点的y坐标的median吗？
把这些点的y坐标排序，可以在O(nlog(n))内完成
然后取中点就行了！ |
|
d****n
发帖数: 1637 | 23 That would be only the partial answer.
if the sequence/array to be sorted has very good randomness(pivot good),
then the O(Nlog(N)).
if the array has been almost sorted or bad chose of pivot, the run time
would be O(N^2).
The Glib C qsort is a text-book implementation, which is terrible slow on
sorting on huge data set.
See introsort. or C++ stl::sort if you are looking for a industry solution. |
|
T********i
发帖数: 2416 | 24 刚开始start, end, length都一样，就是有3000票候选。是log(n)么？
当然你可以argue只选第一张就好了。但是将来不一定，尤其是有退票。
退票可能会concat其他碎票。也是O(n)的。
其实这个可以证明最多就O(n)。O(nlog(n))都不对。
你的分析对不对是原则问题。
了。 |
|
w******w
发帖数: 126 | 25 quick sort time complexity 是 O(log(n))? 竟然跟binary search 一样了？ 难道
我以前的知识都学错了？ 不是 nlog(n) 吗？
OCaml |
|
m********4
发帖数: 1837 | 26 No.1 is about one dimensional random walk. It's a classic problem. I
remember the process is too long. It depends on the specific situation. Do
you need to write down all the algebraic process or could you employ some
available formulas?
In the area of probability, you need use binomial distribution and the
approximation to n factorial: n! is roughly equal to sqrt(2*Pi*n)(n/e)^n.
I dont know the proof w.r.t. graph theory. The first time I knew this
problem I only knew probablity and ... 阅读全帖 |
|
c******r
发帖数: 300 | 27 If the numbers are ordered, then you can solve this problem by dynamic
programming with O(N^2)
complexity. Otherwise I thought it is a NP-Complete problem. and of course
by the nature of this problem,
there are many ways to reduce the complexity.
Why you need the number to be ordered if the dp already costs O(N^2)? It
seems you can always sort it in O(Nlog(N)). I am also not quite sure why
this is a NPC problems, the bound 1.5 is somehow crucial here. Otherwise,
you probably are right, it must b |
|
z****g
发帖数: 1978 | 28 可以直接suppose array is increasing?你这可直接就把nlog(n)给扔了... |
|
z****g
发帖数: 1978 | 29 2. 如果array是没有sort的，最好的应该是nlog(n)了。
3. n位2进制计数器累加
4. std::set.find() |
|
l*******l
发帖数: 248 | 30 如果是sorted 的array，很容易check是increasing还是decreasing的吧，看看前两个
element谁打就好了吧
可以讲讲如果没有sort过，这道题怎么做吗？为什么是nlog(n)？ |
|
z****g
发帖数: 1978 | 31 ...先sort一次呗，你不觉得nlog(n)眼熟么？ |
|
w*******x
发帖数: 489 | 32 当场想晕了，只好给了个Nlog(N)算法。
哎。写写才记得。O(N):
#include
using namespace std;
int main(int argc, char *argv[])
{
int x[20];
for(int i=0;i<20;i++)
x[i]=rand()%100-50;
int i=0;
int j=0;
int im=0;
int jm=0;
int max=-1;
int sum=0;
//最大求和子序列
for(j=0;j<20;j++)
{
sum+=x[j];
if(sum>max){max=sum;im=i;jm=j;}
if(sum<0){i=j+1;sum=0;}
}
for(int i=0;i<20;i++)cout<
cout<<"max="<阅读全帖 |
|
a****y
发帖数: 99 | 33
my 2cents,use AVL tree, plus each node store the number of node of the sub-
tree.so that median finding costs log(m). insert, delete also costs log(m).
O(nlog(m) )
I google it and find some reference :
Comparison of algorithms for standard median filtering
Juhola, M. Katajainen, J. Raita, T.
Signal Processing, IEEE Transactions on
Jan. 1991, Volume: 39 , Issue: 1, page(s): 204 - 208
Abstract
On computation of the running median
Astola, J.T. Campbell, T.G.
Acoustics, Speech and Signal Proc... 阅读全帖 |
|
n******t
发帖数: 4406 | 34 含n个点的平面点集的convex hull可以在O(nlog(n))解出来,然后包住it的最小圆可以
在O(n)时间内解出来。所以你的方法还是work的。不过，如果都想到这里，自然就会发
现没有必要解convex hull了,因为从convex hull到找最小园的用的思路也就是这个问
题的优化算法的思路了。 |
|
d*z
发帖数: 150 | 35
the len of r and s are no more than 2n
so
First we can get x+y=r-s+1 in O(n)
The time to get u=(x+y)(x+y)-4r is O(nlog(n)).
and the time to find x-y=sqrt(u) should be O(
n*log(n)log(n)log(log(n)) ).
so I think the time is O( n*log(n)*log(n)*log(log(n)) ).
Of course it is less than O(n*n). That's in polynomial time.
But in the fact, the comment algorithm to multiply and divid
is both O(n*n).
As to the sqrt(), we can use
x(n)=(x(n-1)*x(n-1)+a)/(2*x(n-1))
to found the sqrt(a), we only need to iter |
|
q**j
发帖数: 10612 | 36 请问你怎么算的nlog(n)和 n?我对这个计算很感兴趣。多谢了。
均每个symbol对应的数据长度.
solution里面的排序的确比较慢. 如果对应的数据较少第二种solution里面独立算sign
(), max(), 相乘, 取== 的成本比较高. |
|
s*****n
发帖数: 2174 | 37 大体估计的.
我那个solution, 不算最内层的abs(), 就是一个排序, 排序整体是 nlog(n).
oloolo给的solution, 避免了排序, 但是有sign(), max(), *, == 四个线性操作, 所
以是4n.
我们两个的外部结构都一样.
sign |
|
m*********k
发帖数: 10521 | 38 成功奖励 20 伪币的用户:
Candysour, cesuoluobo, happened, chriraus, papalan, xfbhs, smartrice, lucan,
hungry1, lonesomex, linzhp, acidia, dongfeiwww, wonder007, ahchzg,
fossilfield, zhanglaosan, cokezero, fleer, mingxiaot, itsbeautiful, wywxm,
SinoGator, wyxbj, missbear, FAQ, BlackQueen, daemonself, hUrtU, JianlianYi,
zzwhe, krillasn, wowow, feiyue2011, frada, Adaaa, wenkefeiwu, fineart,
tudoudou, sweetmilk, Taraxacum, babyface1982, chopstick14, faintcat,
hellobruce, josephotto, lucan, wingsheart
奖励版面:(Ap... 阅读全帖 |
|
m*********k
发帖数: 10521 | 39 成功奖励 20 伪币的用户:
Candysour, cesuoluobo, happened, chriraus, papalan, xfbhs, smartrice, lucan,
hungry1, lonesomex, linzhp, acidia, dongfeiwww, wonder007, ahchzg,
fossilfield, zhanglaosan, cokezero, fleer, mingxiaot, itsbeautiful, wywxm,
SinoGator, wyxbj, missbear, FAQ, BlackQueen, daemonself, hUrtU, JianlianYi,
zzwhe, krillasn, wowow, feiyue2011, frada, Adaaa, wenkefeiwu, fineart,
tudoudou, sweetmilk, Taraxacum, babyface1982, chopstick14, faintcat,
hellobruce, josephotto, lucan, wingsheart
奖励版面:(Ap... 阅读全帖 |
|
t******q
发帖数: 117 | 40 【 以下文字转载自 EE 讨论区,原文如下 】
发信人: TigerJade (小人莫不有才), 信区: EE
标 题: Re: 还是请教关于DCT用于图像压缩。这么说吧？
发信站: Unknown Space (Fri Aug 22 15:50:35 2003) WWW-POST
my 2 cents. Although you can always treat linear transform in matrix
multiplicatoins, you have no way to implement it in the same manner, due to
the high complexity of the matrix multiplication ~ N^3. That why we love DCT
or DFT, because they are on the order of Nlog(N). If I remember correctly, the
complexity of DWT is KN, where K is the length of the fi |
|
