|
F**********r
发帖数: 237 | 2 这回这个问题可能和具体实现有关，就是k-way merge。
1）首先如果能够全部load进内存，是不是其实最好就是依序把它们放进连续内存，然
后直接sort。O(nlogn)
如果用heap的话，要么就是heap的每个element要有data+index（2.1),要么就是要有一
个size k的array存放每个array的active index,但是要决定具体要advance which
array的时候，worst case要把size k array所指向的element和heap top比较一次(2.2
)：这本身复杂度就是k*n了。。。。另外虽然heap move down直接成堆复杂度是O(n),
但并不适用在这个case。也就是说用堆的话复杂度是O（nlogk)+ 更多内存 或者 O(n*k
).
这个理解对么？大家怎么看？ |
|
l*****g
发帖数: 685 | 3 heap适用于search最大或最下k个值；BST是适用于search任意一个值
如果数组有序，构成BST的time complexity是O(n); 如果无序，是O(nlogn);
如果数组有序，那该数组本身就是个heap (ascending --> min-heap; descending -->
max-heap), 无须再改变，no time complexity; 如果数组无序，构成heap是 O(
n);
好像没有O(logn)实现heap 和 BST 的方法 |
|
a***9
发帖数: 364 | 4 BST就是存排好序的一组数，而基于比较的排序算法没有低于O(nlogn)的。
建堆只需要O(n)，所以不能指望堆是有序的。
BST时间空间开销大，通常都是存所有的数据量，在预见需要保留所有数据
信息量的时候得用BST。堆信息量小一些，但是在处理海量数据或者流时不
好存所有数据，而且也不需要保留所有数据的信息量，只需要最大最小的k
个之类的，这时候用堆比较划算。 |
|
w********n
发帖数: 13 | 5 1. n个球,n很大 > 1billion, k个颜色, k相对小， 比如10. 要求in space sort最
efficient的做法 白板coding. （hint, k<< n 所以最后算法争取比nlog(n)小)
该题的第二问 k = 1000 实现比nlogn 更efficient的in space的算法
另外 还有elevator设计 不同楼层多个button都按下了 如何处理 多个电梯 如何处理 |
|
g*****i
发帖数: 2162 | 6 恩,不连续的一般是O(nlogn),不知道算法的话用dp是o(n^2) |
|
g***s
发帖数: 3811 | 7 非负整数数组 is ok for binary search..
yes if all x[i] are non-negative numbers (integer is not required)
same.
O(K*N*N)
Non-negative numbers can be handled by binary search in O(N*N).
sum(i,j) : sum of (a_i, a_i+1,..,a_j) O(n*n)
sort sum(i,j) O(nlogn)
binary search in the sorted sum(i,j) O( n log n)
Total time is O(n^2) |
|
g***s
发帖数: 3811 | 8 In your description, in 1, it is O(n log n), isn't it?
In 2, how can you use log(n) to find the x,y?
for pipe=1, the answer is the weighted median, it is O(n).
Then for pipe=2, the total time can be O(nlogn) using weighted median +
binary search. |
|
g**e
发帖数: 6127 | 9 this is not right even for pipe=1, your algorithm yields O(nlogn) for p=1 |
|
z*******y
发帖数: 578 | 10 为什么要排序？
只用hashtable 就可以了吧：
一个一个记录读，先检查时间 如果时间是24小时以内，用pageurl 做hashtable的key
，value就是一个list来存所有的userid。 如果记录总共有N条，时间复杂度就是O(n)
。你一排序就增加了复杂度，至少要O（nlogn）,而且还改变了源文件顺序 |
|
h*****g
发帖数: 944 | 11 convert a random array to BST: o(nlogn)
insertion: o(logn)
deletion: o(logn)
貌似deletion有三种情况，
1 Deleting a leaf (node with no children): Deleting a leaf is easy, as we
can simply remove it from the tree.
2 Deleting a node with one child: Remove the node and replace it with its
child.
3 Deleting a node with two children:
这三种情况不都是O(logn)吧？ |
|
f*****w
发帖数: 2602 | 12 只能想出NlogN的 先按照线段左端的点排序 然后走一遍
不知道怎么样还能更好的没有 |
|
x********o
发帖数: 519 | 13 can you say more details about your approach.
I do not think it is NlogN. |
|
g*********e
发帖数: 14401 | 14 my solution.
sort the start & end O(nlogn)
then
O(n) time to get the length.
do a traversal,
use a variable (t) to store level of interleaving at the current position.
once encounter a start, t++,
once encounter an end, t--,
add the accumulated length at each step as long as t>0 |
|
d*******l
发帖数: 338 | 15 如果要统计两两overlap的总对数，那用线段树应该能O(nlogn)出来。如果要输出所有
，那只能O(n^2)了 |
|
t**k
发帖数: 260 | 16 Just sort all the starting points and ending points.
Then traverse the list in the increasing order:
if get a starting point, put the corresponding interval into a hash set, and
output all the intervals that start with this starting point and end with
the ending points of the intervals that are in the hash set;
if get an ending point, just remove the corresponding interval from the hash
set.
So the time complexity should be O(nlogn+m) where m is the number of
overlapped intervals? Btw, m could b... 阅读全帖 |
|
d*******l
发帖数: 338 | 17 想到如下方法：
1. 按区间起点排序
2. 离散化，总共不超过2n个端点，重新编号为0 - 2n-1
3. 遍历所有区间，对每个区间，计算(start, end)区间中起点的个数，累加到结果中
4. 单独计算起点重合的情况
离散化之后，可以用O(n)空间记录起点的分布，如果用O(n)预处理一下sum[i]，第三步
只需要O(1)时间。并且能处理区间端点不是整数的情况。只有第一步是O(nlogn)的，其
他都是O(n)。这样有什么bug吗？ |
|
d*******l
发帖数: 338 | 18 如果要输出所有的pairs，那没有什么好办法，因为这样的pairs最多有O(n^2)个，我们
不可能做的比这个更好。直接排序之后，每个区间往后找就行了，再精巧的方法也不会
从本质上降低复杂度。
我说的是计算overlap pairs数目的方法。这个是可以O(nlogn)时间计算出来的。 |
|
g**u
发帖数: 583 | 19
恩， 这个很好理解， 谢谢了。
如果要返回所有的overlap的区间的pair的话， 可不可以直接这样：
对按起点排好序之后的区间， 对每个区间， 用binary search寻找在它后面所有与之
overlap的区间。
我们有n个区间， 每个区间寻找overlap的区间是 log n, 排序的复杂度是 nlog n，所
以总的复杂度依然是 o(nlogn).
不用interval tree 也可以做到。
但是如果我们有stream of intervals的话， interval tree估计派上用场了。 |
|
d*****o
发帖数: 28 | 20 //Notes: may have bug, just show the ideas
Can not input in Chinese, so write in English -
Q1: code:
for k =3, psedocode: // (O(N^2))
input: A[], S
Arrays.sort(A); // O(NlogN)
for(int i = 0; i < A.length-2; i++) // O(N^2)
{
// set A': A - A[i]
findIt(A[i], S-A[i], A'); // find two element in A -A[i] sum to S -
A[i], O(N)
}
DP solution:
// not exactly the solution, just to decide how many K elements sum to
// a value S
input A[], N, K, S
N- size of the array
K- number of elements... 阅读全帖 |
|
g*******i
发帖数: 95 | 21 我有一个思路，是不是可以用类似于MergeSort的方法递归达到O(nlogn)
合并相邻的两个处理过的数列比如
x1,x2,x3,y,y,z1,z2,z3, 和 X1,X2,Y,Z1,Z2 (xi<0,y==0,z>0)
（1）反转z1到X2
（2）反转X1到X2，反转z1到z3
(3) 移动X1,X2到x3后，移动z1,z2,z3到Z1前，当中元素改为y==0
大家觉得有什么问题么？ |
|
h***o
发帖数: 30 | 22 Expected complexity是O(nlogn), partition很精简常数小， in-place, 每次逐个扫
数据
(cache miss少) |
|
d*******l
发帖数: 338 | 23 greedy确实是不对的，有O(nlogn)的dp做法
[1
interval |
|
d*******l
发帖数: 338 | 24 后来又想了想，如果这题每个工作都认为是具有相同价值的，确实就是贪心法的例题。
。。我之前遇到过的是每个工作还有个权值，让找出总权值最大的方案，这就能用到O(
nlogn)的dp了 |
|
f*********i
发帖数: 197 | 25 A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bianry tree找两个节点的最
小公共父亲, 一开始是允许有父节点的,然后扩展到没有父亲节点,我给了O(nlogn)解法
public static BinaryTree tree_least_comm... 阅读全帖 |
|
d*******r
发帖数: 208 | 26 my bad. my revision won't work.
Wrote an nlogn code.
Node* LowCommonAnc(Node *node, Node *node1, Node *node2){
if(node==NULL || node1 == NULL || node2 == NULL) { return NULL; }
if (node == node1 || node == node2) { return node; }
if (isChildren(node->left, node1) && isChildren(node->left, node2)) {
// both go left
return LowCommonAnc(node->left, node1, node2);
} else if (isChildren(node->right, node1) && isChildren(node->right,
node2)) {
// both go right
... 阅读全帖 |
|
a*****a
发帖数: 46 | 27 排序呢？O(nlogn) time, O(1) space.
typedef pair ids;
bool cmpIds(ids a1, ids a2) {
return (a1.first < a2.first);
}
int maxDistance(int a[], int n) {
vector numid;
for(int i=0; i
numid.push_back( make_pair(a[i], i) );
sort( numid.begin(), numid.end(), cmpIds );
int maxd=0;
for(int i=1; i
int d = numid[i].second - numid[i-1].first;
if (d<0) d*=-1;
if (d>maxd) maxd = d;
}
return maxd;
} |
|
s**x
发帖数: 7506 | 28 14.3-4
given an interval tree T and interval i, describe how all intervals in T
that overlap i can be listed in O(min(n, klogn)) time, where k is the number
of intervals in the output list. (optional: find a solution that does not
modify the tree)
14.3-7
VLSI databases commonly represent an intergrated circuit as a list of
rectangles, assume that each rectangle is rectilinearly oriented(side
parallel to the x- and y-axis), so that a representation of a rectangle
consists of its minimum and maxim... 阅读全帖 |
|
s**x
发帖数: 7506 | 29 not really. for this one, there is a better way.
discussed before and also on the web. the idea is split each pair and then
sort all the numbers and the walk through the list.
thinking about lost of "()", if will be nested if there is a overlap. O(
nlogn). |
|
a**********2
发帖数: 340 | 30 来自主题: JobHunting版 - 问道排序题 不能用swap，只能用给定的function
reverse(i): reverse first i element in array.
有没有O(nlogn）解啊? |
|
a**********2
发帖数: 340 | 31 来自主题: JobHunting版 - 问道排序题 可能average是O(nlogn)就可以了吧
我当时给的解法就是O(n^2)
对i<- n to 1
找到1到i里面最大的值arr[j]然后reverse(j),reverse(i)
明显他不满意，后来说quicksort，选第一个或者最后一个做pivot好像不行，如果题目
改成reverse(i,j)就好了 |
|
f*********1
发帖数: 75 | 32 来自主题: JobHunting版 - 问道排序题 exchange(i,j){
reverse(i,j);
reverse(i+1,j-1);
}
so nlogn ? |
|
p*****u
发帖数: 310 | 33 给定一个数字数组 (Let's call it count-array) ，其中每个元素是从末端数小于原
数组中该元素的个数。求原数组。原数组中元素是从1到n。
Example:
原数组 4,1, 3, 2
Count array 3, 0, 1, 0
求nlogn的算法。 |
|
P**********c
发帖数: 3417 | 34 就跟前面指出的，这个不是O(nlogn)。vector里remove一个element的复杂度是O(n), 所以这个算法是O(n^2). 另外你这个有序数组里找第k大的数写复杂了，应该就像刚来Java那个，const time.
另外我觉得G家的题目不能用STL做。否则它肯定会问你STL是怎么实现的，这个更容易出错。 |
|
m****t
发帖数: 555 | 35 实际上，因为本题vector里的数据是序的，所以remove操作可以用binary search。
这样一来复杂度就是nlogn。
只不过这样一来我们不能使用标准的vector，需要自己 写code实现。
所以这个算法是O(n^2). 另外你这个有序数组里找第k大的数写复杂了，应该就像刚
来Java那个，const time.
易出错。 |
|
m****t
发帖数: 555 | 36 总结一下，用一个vector存放1...n。
从头到尾扫描给定的数组，每得到一个值，从vector里删掉。因为vector里数据是有序
的，因此remove操作可以使用二分法，复杂度为O(logn).
这样本算法复杂度为O(nlogn). |
|
a**********2
发帖数: 340 | 37 可以用merge sort(desc)吧
思路更简单：
merge 的时候对于前半部分的元素i和后半部分的元素j
如果input[i] >= input[j] 那么i对应的元素的count就应该增加 high-j+1
这样每次merge的时候都保证后半部分比他小的元素被加进来了
worst case也是O(nlogn） |
|
d*******l
发帖数: 338 | 38 我记得POJ上有一道一模一样的题，是典型的线段树/树状数组的题，线段树可以做到
nlogn，树状数组nlog^2n。我应该A掉了，方法就是用线段树维护一个区间内还剩下的
点的个数。 |
|
f**********t
发帖数: 1001 | 39 有没有更好的做法？
Brute force method:
sort the array using any existed sort algorithm, just treating the array as
normal array. The best time complexity is O(nlogn)
Method2:
Among M sorted array, select the smallest number from one array, move the
pointer to the next integer of the array. repeat this routine, until all
integers are put into order.
For each integer in the output array, it's compared M times. the time
complexity is O(n*M)
The code is listed below:
void nwaymergesort(int* arr, int* out, in... 阅读全帖 |
|
q****x
发帖数: 7404 | 40 is it possible?
if yes, how?
if not, why? |
|
g***s
发帖数: 3811 | 41 yes. since getting the median is O(n) and you can you the median to do
partition. |
|
q****x
发帖数: 7404 | 42 you mean use that worst case O(n) get_median() algorithm? cool. |
|
|
|
d*******l
发帖数: 338 | 45 矩形那个题，这里只说通过overlap形成一个不规则图形的若干个矩形。假设有n个，那
这n个矩形最多有2n条垂直的边。这2n条垂直的边所在的直线和最后图形的交点处才可
能形成分界点。把这些直线按坐标排序，然后用这些直线把原来的那些矩形分成更小的
矩形，把小矩形排序。然后确定每个小区间上的高度，最后扫描一下这些小区间，前后
出现高度差的就构成一个分界点。应该可以做到O(nlogn)。
(i |
|
d*******l
发帖数: 338 | 46 这种题面试最多说说思路，不太可能写出code。。
你说的对。感觉上像是有nlogn办法，不过要求的是边界点，细节不太好办，你能具体
说说你的方法吗？ |
|
m**q
发帖数: 189 | 47 Looks like an old question, but failed to find a better solution than O(klg(
m+n)). Any ideas?
The question is quoted from a comment on ihas1337code website
------
1.Two reverse sorted arrays A and B have been given. such that size of A is
m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n It can be done in O(n*n) but i believe it
can be done in a very efficient way. I heard someone say there is a paper
from SODA. I... 阅读全帖 |
|
c****p
发帖数: 6474 | 48 若随机变量X的概率密度为Px，Y的概率密度为Py，则（X+Y）的概率密度为conv(Px,Py)
。
以上适用于连续密度函数。我用两个骰子扔点验证了一下，好像还是正确的。
理论上当然也是正确的。
令Z=X+Y，则P(Z==z) = P(x==1)*P(y==z-1) + P(x==2)*P(y==z-2)...+P(x==z-1)*P(y=
=1)
这个恰好就是卷积的定义。
鉴于MATLAB里面算卷积很方便，我就用它算了一下。
实现得好的话，卷积的复杂度是NlogN，不好的话是N^2，N为卷积序列长度。好像不比穷
举快多少。。。 |
|
b*******8
发帖数: 37364 | 49 离散卷积NLogN算法有Wiki页面吗？我只找到积分形式的连续函数卷积（咱面试用不到
）。
Py)
y=
比穷 |
|
f*********i
发帖数: 197 | 50 求一个unsorted数组中最长的等差数列（int 数组，可递增或者递减）
如果是求unsorted的最长递增或者递减串，那么是有一个nlogn的方法，加上等差这个
条件，估计要是n2了。
我在想是不是一开始可以用动态规划的方法，创建几个数组A和B，假设原始数组为C,那
么Ai是Ci左边第一个比Ci小的数，Bi是Ci又变第一个比Ci大的数，然后通过这两个辅助
函数查找。
好像到这里就卡住了，有没有高人给个解法我？ |
|
