y*****3
发帖数: 451 | 1 到底咋个写法？谁能给贴个code？我就想不通，linkedlist的in-place merge sort怎
么能到O(n log n)呢？？又不是array |
|
|
s******7
发帖数: 1758 | 3 这道题用recursion merge sort要容易得多， 也能通过leetcode的oj
如果要一定iterative, bottom-up,要预判各种极端情况， 非常繁琐，面试的那一个小
时估计搞不出来，我写了一会就放弃了， 不钻牛角尖。
有时候bottom up 和 top down 算法上都可行，可coding 两者起来就差老远了 |
|
s********u
发帖数: 1109 | 4 就利用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 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 以及Find Median Of Two Sorted Arrays。 复杂度是logM+logN还是logK?我觉得是
logM+logN，为什么有人说logK?
这道题一直不想看。但据说是高频。终于在2013末看懂了。 |
|
m**********n
发帖数: 97 | 7 对啊，可是merge sort算递归吧，不是一般递归都是需要O（n）space吗
pointer |
|
m**********n
发帖数: 97 | 8 我在cracking the code interview上看到说merge sort的空间复杂度是depends，能不
能给解释下为什么是log n |
|
d********e
发帖数: 239 | 9 leedcode上的题目sort list
space要求O(1)
找了半天，都是recursive的方法
请哪个大牛能贴一个iterative的代码吧
谢谢 |
|
c*******7
发帖数: 438 | 10 那样应该需要O(n^3)了吧？用Bubble sort更快一些。 |
|
|
l*****a
发帖数: 14598 | 12 character set固定的话，counting sort 可以吗
另外它希望怎么输出呢 |
|
|
b*****c
发帖数: 1103 | 14 是每行每列分别有序，不是将matrix视作array的有序，
前者是sorted matrix的数学定义，后者是不知出处的定义 |
|
b*****c
发帖数: 1103 | 15 是每行每列分别有序，不是将matrix视作array的有序，
前者是sorted matrix的数学定义，后者是不知出处的定义 |
|
|
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 sorting with 3 stacks.
all numbers are initially in stack one.
no other space allowed.
回答了一个O(N^2)的方法, 要问一个更小的. |
|
u*a
发帖数: 247 | 21 It's basically a merge sort. O(nlogn). |
|
z***b
发帖数: 127 | 22 这个怎么用三个stack 实现merge sort? |
|
u*a
发帖数: 247 | 23 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) |
|
|
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) |
|
|
b********r
发帖数: 620 | 31 blaze大牛当时讲了一下，就是不停的build heap，保证取前k个。
用quick sort可能也可以 |
|
|
x*****0
发帖数: 452 | 33 其实就想看看多线程处理，比如一个线程负责io，一个负责sort，能不能speed up |
|
x*****0
发帖数: 452 | 34 不知道这样行不行。不能全部放入内存，但是可以部分放入内存。
三个buffer，其中两个负责存储分别从文件中
读来的数据（每次读整个buffer size的数据），
另一个负责存储sort结果。
开一个线程负责两个buffer的读，并且排序。
开另一个线程负责写第三个buffer（一旦满了以后）中的数据到结果文件中，
并且负责清空。 |
|
l******s
发帖数: 3045 | 35 how about idea of Merge Sort |
|
|
j***y
发帖数: 1640 | 37 老夫的粗快猛的 搞法 是， 先 merge 成一个sorted list. 再取中值就容易了。 |
|
p******r
发帖数: 122 | 38 感觉它在找出最大的key 的时候就sorting 了吧。或者这个题目也可以是如何很快的找
出最大的 key. |
|
k****r
发帖数: 807 | 39 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
一般情况都是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和名字有什么风险吗？让对方转
钱进来。先谢了！ |
|
|
s********g
发帖数: 370 | 44 想着赶八月一，昨晚寄的over night, 今天早上delivered,但是律师是寄到了sorting
center。这样是算赶上了还是没呢？ |
|
|
|
f*o
发帖数: 654 | 47 and depends on the array sorted or not
hehe |
|
j*****s
发帖数: 80 | 48 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 if you are in industry, quick sort is enough. |
|
g******r
发帖数: 37 | 50 找出value最大的key为毛要sort啊？
linear scan一下不就行了？ |
|
