由买买提看人间百态

topics

全部话题 - 话题: sorts
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
y*****3
发帖数: 451
1
来自主题: JobHunting版 - leetcode上的Sort List那道题
到底咋个写法?谁能给贴个code?我就想不通,linkedlist的in-place merge sort怎
么能到O(n log n)呢??又不是array
s**x
发帖数: 7506
s******7
发帖数: 1758
3
来自主题: JobHunting版 - leetcode上的Sort List那道题
这道题用recursion merge sort要容易得多, 也能通过leetcode的oj
如果要一定iterative, bottom-up,要预判各种极端情况, 非常繁琐,面试的那一个小
时估计搞不出来,我写了一会就放弃了, 不钻牛角尖。
有时候bottom up 和 top down 算法上都可行,可coding 两者起来就差老远了
s********u
发帖数: 1109
4
来自主题: JobHunting版 - leetcode上的Sort List那道题
就利用merge two sorted lists那题的函数啊
ListNode *sortList(ListNode *head, int size){

if(size<=1) return head;

ListNode *prev = NULL, *cur = head;

for(int i = 0; i < size/2; i++){
prev = cur;
cur = cur->next;
}

if(prev) prev->next = NULL;

return mergeTwoLists( sortList(head,size/2), sortList(cur,size -
size/2) );

}

ListNode *sortList(ListNode *head) {

int ... 阅读全帖
S******6
发帖数: 55
5
来自主题: JobHunting版 - leetcode上的Sort List那道题
pass了,不过不是replace
class Solution {
public:
ListNode *sortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
vector res;
if(head == NULL || head->next == NULL) return head;
ListNode *cur = head;
while(cur)
{
res.push_back(cur->val);
cur = cur->next;
}
sort(res.begin(), res.end());
ListNode ... 阅读全帖
h**o
发帖数: 548
6
来自主题: JobHunting版 - 关于求the kth smallest in two sorted array
以及Find Median Of Two Sorted Arrays。 复杂度是logM+logN还是logK?我觉得是
logM+logN,为什么有人说logK?
这道题一直不想看。但据说是高频。终于在2013末看懂了。
m**********n
发帖数: 97
7
来自主题: JobHunting版 - sort list java solution
对啊,可是merge sort算递归吧,不是一般递归都是需要O(n)space吗

pointer
m**********n
发帖数: 97
8
来自主题: JobHunting版 - sort list java solution
我在cracking the code interview上看到说merge sort的空间复杂度是depends,能不
能给解释下为什么是log n
d********e
发帖数: 239
9
来自主题: JobHunting版 - 请教iterative merge sort list的代码
leedcode上的题目sort list
space要求O(1)
找了半天,都是recursive的方法
请哪个大牛能贴一个iterative的代码吧
谢谢
c*******7
发帖数: 438
10
来自主题: JobHunting版 - 请教iterative merge sort list的代码
那样应该需要O(n^3)了吧?用Bubble sort更快一些。
x****g
发帖数: 1512
l*****a
发帖数: 14598
12
character set固定的话,counting sort 可以吗
另外它希望怎么输出呢
d********i
发帖数: 582
13
某大牛的solution是参考MIT做出来的,但是我不理解findMedian(B, A, Math.max(0,
mid-m), Math.min(n-1, mid))中的Math.max(0, mid-m)和Math.min(n-1, mid)是做什
么用的?
代码在这里:http://n00tc0d3r.blogspot.com/2013/04/median-of-two-sorted-arrays.html
MIT的note在这里:http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf
b*****c
发帖数: 1103
14
来自主题: JobHunting版 - find kth element in n*n sorted matrix
是每行每列分别有序,不是将matrix视作array的有序,
前者是sorted matrix的数学定义,后者是不知出处的定义
b*****c
发帖数: 1103
15
来自主题: JobHunting版 - find kth element in n*n sorted matrix
是每行每列分别有序,不是将matrix视作array的有序,
前者是sorted matrix的数学定义,后者是不知出处的定义
r*******k
发帖数: 1423
16
来自主题: JobHunting版 - 谁能给解释一下patience sort解LIS?
http://wordaligned.org/articles/patience-sort.html
完全没看懂
如果序列是1,2,3,0,4
按他的方法
pile 1: 4,0
pile 2: 3,2,1
那得到的不就是3了么?
另外,哪个animation里面,highlight出来的card是什么意思?
y***e
发帖数: 32
17
如何找到这个pair,有O(log n)的解法吗?
Sorted的队列包含duplicate元素.
s********e
发帖数: 340
18
原文在这里:
http://www.programcreek.com/2013/02/leetcode-merge-k-sorted-lis
我的理解是,用PriorityQueue将需要合并的一个列表里的元素都加入到这个
PriorityQueue中。
PriorityQueue会自动对所有加入的元素进行排序。
我不明白的是下面这个部分,为什么用q.add(temp.next)再把节点再加入同一个
PriorityQueue中? 完整程序,请看上面给的链接。谢谢! 不太明白下面的部分。
while (q.size() > 0) {
ListNode temp = q.poll();

p.next = temp;

if (temp.next != null)
q.add(temp.next);
p = p.next;
}
u***l
发帖数: 51
19
最优解时间复杂度是 O(n) 吗?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
可能有重复值
l******g
发帖数: 188
20
来自主题: JobHunting版 - Groupon一个店面题. sort with 3 stacks.
sorting with 3 stacks.
all numbers are initially in stack one.
no other space allowed.
回答了一个O(N^2)的方法, 要问一个更小的.
u*a
发帖数: 247
21
来自主题: JobHunting版 - Groupon一个店面题. sort with 3 stacks.
It's basically a merge sort. O(nlogn).
z***b
发帖数: 127
22
来自主题: JobHunting版 - Groupon一个店面题. sort with 3 stacks.
这个怎么用三个stack 实现merge sort?
u*a
发帖数: 247
23
来自主题: JobHunting版 - Groupon一个店面题. sort with 3 stacks.
Assume you have two sorted stacks, you can merge them into the third stack.
Now do it recursively.
y*****e
发帖数: 712
24
很多家都有这题,假如有很多points,找出离原点最近的k个点。
做法就是建个size为k的heap, 建heap的complexity是o(k), 对后面n - k的点,还有
insert/pop operation的complexity是(n-k)log(k), 综合下来是nlogk
另外一种方法是任意去pivot, 每次call partition function, 把数组按放到pivot的
左边和右边,一直到pivot = k为止,直接return pivot左边的所有点。这种做法应该
是每次去掉一半的数组
n + n/2 + n/4 +.... = 2n也就是o(n),
应该是selection sort更好啊,为啥面试官总是让写heap? 是不是有其他的考量?比如
是streaming data或者数据量太大,不能一次完全放到array里?
h****3
发帖数: 89
25
这个问题很好,感觉一改改就变系统设计了
我觉得楼上几位分析的很对,如果你有海量数据,维持k个固定space应该会更优;但如
果数据量有限,selection sort会更好
g******n
发帖数: 10
26
你的第二种方法最坏情况下时间复杂度是 O(n^2),不是 O(n),因为不是每次都刚好把
数组分成长度相当的两半,最坏情况下两边长度分别是 0 和 n-1,所以 T(n) = T(n-1
) + O(n),总的时间复杂度是 O(n^2). 另外这种方法也不叫 selection sort,而是
叫做 randomized-select,因为过程跟 randomized-quicksort 的 partition 非常相
似,期望时间复杂度是 O(n)。详细内容可以看 CLRS pp. 215,  §9.2
Selection in expected linear time
k****r
发帖数: 807
27
是这个题吗?
Sort a list in which each number is at MOST distance k from its actual
distance.
min heap, space O(k)
w***y
发帖数: 6251
28
多谢! 其实我也不知道具体要求,就是看到这个题面,讨论什么的都有 😓
http://www.glassdoor.com/Interview/Sort-a-list-of-numbers-in-wh
k****r
发帖数: 807
29
是这个题吗?
Sort a list in which each number is at MOST distance k from its actual
distance.
min heap, space O(k)
w***y
发帖数: 6251
30
多谢! 其实我也不知道具体要求,就是看到这个题面,讨论什么的都有 😓
http://www.glassdoor.com/Interview/Sort-a-list-of-numbers-in-wh
b********r
发帖数: 620
31
blaze大牛当时讲了一下,就是不停的build heap,保证取前k个。
用quick sort可能也可以
s***c
发帖数: 639
32
来自主题: JobHunting版 - 合并two big sorted files
external sort
x*****0
发帖数: 452
33
来自主题: JobHunting版 - 合并two big sorted files
其实就想看看多线程处理,比如一个线程负责io,一个负责sort,能不能speed up
x*****0
发帖数: 452
34
来自主题: JobHunting版 - 合并two big sorted files
不知道这样行不行。不能全部放入内存,但是可以部分放入内存。
三个buffer,其中两个负责存储分别从文件中
读来的数据(每次读整个buffer size的数据),
另一个负责存储sort结果。
开一个线程负责两个buffer的读,并且排序。
开另一个线程负责写第三个buffer(一旦满了以后)中的数据到结果文件中,
并且负责清空。
l******s
发帖数: 3045
35
来自主题: JobHunting版 - 合并two big sorted files
how about idea of Merge Sort
x*****0
发帖数: 452
36
来自主题: JobHunting版 - 合并two big sorted files
external sort 应该可以
j***y
发帖数: 1640
37
来自主题: JobHunting版 - 求代码,median of K sorted list
老夫的粗快猛的 搞法 是, 先 merge 成一个sorted list. 再取中值就容易了。
p******r
发帖数: 122
38
感觉它在找出最大的key 的时候就sorting 了吧。或者这个题目也可以是如何很快的找
出最大的 key.
k****r
发帖数: 807
39
来自主题: JobHunting版 - Leetcode有没有External sort的题型?
public static void main(String[] args) {
int[] A = {1,2,5,2,1,0};
// mergeSort(A);
for (int i : A) {
System.out.print(i + ".");
}
}
写个 mergeSort 看看输出是不是sort的就可以了。
z*********n
发帖数: 1451
40
来自主题: JobHunting版 - topological sorting BFS和DFS都要会吗?

一般情况都是dfs方便,尤其是需要打印某串路径,比如打出某个环的。而要判断是否
唯一sort结果,肯定bfs方便吧。比如1->2, 1->3,可以是1 2 3, 也可以是1 3 2,不
唯一。BFS这trivial啊,DFS咋整?肯定也能做出来,但肯定没BFS简单。
t****4
发帖数: 7500
41
艹, 这标题不改的话封14天。 sort of 条毛
d*******2
发帖数: 340
42
请问告诉对方自己银行的sort code, account number和名字有什么风险吗?让对方转
钱进来。先谢了!
w***n
发帖数: 1519
s********g
发帖数: 370
44
想着赶八月一,昨晚寄的over night, 今天早上delivered,但是律师是寄到了sorting
center。这样是算赶上了还是没呢?
l******n
发帖数: 9344
45
移民局说,我们是按rp sort的
f*o
发帖数: 654
46
来自主题: SanFrancisco版 - sorting问题求教。
heap sort
f*o
发帖数: 654
47
来自主题: SanFrancisco版 - sorting问题求教。
and depends on the array sorted or not
hehe
j*****s
发帖数: 80
48
来自主题: SanFrancisco版 - sorting问题求教。
Depend on the values of N and X, and your requirement on space/time
Assume N is very large, and X is relatively small.
(1) Find the X'th largest number in the list, say, T - using randomized
selection, O(N) time
(2) Go through the list, put numbers larger than T into an array. - O(N)
time, O(X) space.
(3) Sort the array. O(XlogX) time.
Of course, if the original list has many duplicated numbers, it will be a bit more complicated. For example, in step (2), you will probably have an array with siz... 阅读全帖
j******0
发帖数: 558
49
来自主题: SanFrancisco版 - sorting问题求教。
if you are in industry, quick sort is enough.
g******r
发帖数: 37
50
找出value最大的key为毛要sort啊?
linear scan一下不就行了?
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)