由买买提看人间百态

topics

全部话题 - 话题: sorts
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
y*****3
发帖数: 451
1
来自主题: JobHunting版 - leetcode最新的那道题:Sort List
Sort a linked list in O(n log n) time using constant space complexity
是用quick sort吗?有没有更好的解法?
i**********e
发帖数: 1145
2
来自主题: JobHunting版 - leetcode最新的那道题:Sort List
这道题是需要merge sort linked list iterative 的。recursion 用的是 O(log n)
stack space,不过也能通过OJ 的。
不过这道题的意义是让你尝试各种不同的算法。quick sort 也比较有意思,但需要优
化一下才能通过。
http://oj.leetcode.com/discuss/712/meaning-of-constant-space-co
m******r
发帖数: 42
3
来自主题: JobHunting版 - sort list java solution
首先,merge sort即使递归space也是O(log n)不是O(n).其次,
merge sort可以循环不用递归,space就是O(1)了
w****r
发帖数: 15252
4
来自主题: JobHunting版 - [ 每日一课] Sort List
/*
* Sort a linked list in O(n log n) time using constant space
complexity.
*/
public ListNode sortList(ListNode head) {
if(head == null || head.next == null)
return head;

//get the length of the liklist
int count = 0;
ListNode node = head;
while(node!=null){
count++;
node = node.next;
}


//break up to two list
int middle = count / 2;
... 阅读全帖
b*****c
发帖数: 1103
5
来自主题: JobHunting版 - find kth element in n*n sorted matrix
sorted matrix = each row/column is sorted
remember k=O(n^2)
write code to solve in n*lg n
----------------------
O(n^2) is simple and stupid --- QuickSelect
b*****c
发帖数: 1103
6
来自主题: JobHunting版 - find kth element in n*n sorted matrix
sorted matrix = each row/column is sorted
e.g.,
1 6 6
2 7 7
2 8 9
k=7
remember k=O(n^2)
write code to solve in n*lg n
----------------------
O(n^2) is simple and stupid --- QuickSelect!!!!!!!!
t***t
发帖数: 6066
7
this is typical external sorting.
you need a heap to sort the N heads.
c*********h
发帖数: 102
8
原题在这里:
http://www.geeksforgeeks.org/median-of-stream-of-integers-runni
Given that integers are read from a data stream. Find median of elements
read so for in efficient way. For simplicity assume there are no duplicates.
For example, let us consider the stream 5, 15, 1, 3 …
After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5
After reading 4th element of stream - 5, 15, 1, 3 -... 阅读全帖
a***e
发帖数: 413
9
回国一趟回来做题很难进入状态了
Merge k sorted linked lists and return it as one sorted list. Analyze and
describe its complexity.
有人面试碰到这题么?我洋洋洒洒写了很多代码,OJ说Time Limit Exceeded
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
int n = lists.size();
if (n==0) return NULL;
ListNode *ret = lists[0];
for (int i=1; i {
ret = merge2Lists(ret, lists[i]);
}
return ret;
}
private:
ListNode *merge2Lists(ListNod... 阅读全帖
F********y
发帖数: 400
10
来自主题: JobHunting版 - Groupon一个店面题. sort with 3 stacks.
土木转行过来的新人,下面都是我的想法,有错莫喷:
第一次轮流pop1个到两个stack里,然后merge回1号stack,因为merge操作,1号里每两
个元素彼此sorted。
第二次轮流pop2个到两个stack里,然后merge,结果1号里每四个元素彼此sorted。
然后循环直到pop数超过n/2,然后最后一次merge回去就结束了。
g******g
发帖数: 585
11
看了一下geeksforgeeks 的解法,貌似和那个多个sorted linked list merge的解法没
有什么区别,按照这个解决方法之需要行或者列是sorted的就可以了。
http://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise
y*****e
发帖数: 712
12
interface是这个 Iterable mergeKSortedIterators(Iterators[] iters)
也就是给每个array的iterator,然后merge.
我开始想的是用merge k sorted list的办法,用一个heap保存所有的iterator,看哪个
iterator的头个element最小,push to result,然后Move to next element。
需要一个iterator的comparator来sort iterators, 是我的comparator写的不对?还
是heap的operation错了?
不知有人做过这题吗,希望给点建议。。。。
public static class iteratorComp implements Comparator>{
public int compare(Iterator a, Iterator b){
int a1 = 0;
in... 阅读全帖
c**********t
发帖数: 23
13
来自主题: JobHunting版 - External Sorting是哪一道题?
merge k sorted array
其中一个算法是external sort
求内推
S*******C
发帖数: 822
14
来自主题: JobHunting版 - counting sort an array of objects怎么做
10 million的数组,数字是8bit的非负数,排序
count sort搞定
follow up,10 million的item class,item有rating和name,根据rating sort。
rating和上面一样也是8bit unsign.
Amazon intern问题
S*******C
发帖数: 822
15
来自主题: JobHunting版 - counting sort an array of objects怎么做
这样的话是调用Collections.sort()方法,这个是mergeSort()
时间复杂度是O(NlogN) 而不是counting sort 的O(N)
b**********5
发帖数: 7881
16
来自主题: JobHunting版 - 这题应该用bucket sort还是counting sort
这点数据, 当然不要。 但如果人家问你怎么做map reduce median, 就是bucket
sort加sampling。。。
D***r
发帖数: 7511
17
来自主题: JobHunting版 - 合并two big sorted files
对,我那个时候学识浅,不知道external sort
但是也想到了分批sort然后写入外存,然后再merge,意思是一样的
然后他就问怎么从文件里读一部分数据什么的
c**y
发帖数: 172
18
来自主题: JobHunting版 - 求代码,median of K sorted list
两个难点吧
1。2个变成k个
2。array变成list。sorted array可以O(1)去掉一半,但是sorted list的话没有O(1)
的方法能去掉一半,只能是O(n)。
s**********g
发帖数: 14942
19
来自主题: JobHunting版 - Leetcode有没有External sort的题型?
这个你让online judge怎么判定你是用external sort的算法来解的?
不能判定的话 和搞个sort题有啥区别(从test case来说。。)
h*********i
发帖数: 2605
20
【 以下文字转载自 JobHunting 讨论区 】
发信人: huchihaisai (hu), 信区: JobHunting
标 题: 一个NxN矩阵每行每列都sort好,如何排序?
发信站: BBS 未名空间站 (Mon Nov 23 16:26:18 2009, 美东)
我记得以前有人讨论过。一种方法是merge sort, maintain a heap,用时O(n^2logn)
,还有更快的方法么?
m*******a
发帖数: 192
21
来自主题: SanFrancisco版 - sorting问题求教。
If I have N numbers
and I want to find out the top X of them
and sort the top X from largest to smallest,
what kind of sorting algorithm would you recommend? thanks
N********n
发帖数: 8363
22
来自主题: Seattle版 - Wait, you CANNOT sort?
Those of you using Gmail probably notices this for quite a while: it cannot
sort by sender and so on, which has been embarrassingly high-lighted in
their competition with Office for California state business.
As if it's not embarrassing enough, Google ridiculously went out to accuse
California state of cooking the requests to what MSFT could offer to make it
difficult for Google to compete.
"If you ask us to sort your emails, then you are asking too much. In fact
thou shall ask not what Google s
g*****s
发帖数: 727
23
来自主题: Seattle版 - Wait, you CANNOT sort?
sorting sometimes is useful. If I have 1000 mails and I remembered one of
them
is from a user whose name start with 'p' something, I can just sort by user
to
find him out.

more
N********n
发帖数: 8363
24
来自主题: Seattle版 - Wait, you CANNOT sort?

It's inconvenient when you want to see all the senders sorted at the same
time as search only gives result for one sender. A sorted view makes it
easier to clean up or re-organize your mail box. It's a limitation when
optimizing for search over other indexing. Funny Google chose to blame
customers instead of admitting it's their own problem.
e*********6
发帖数: 3453
25
每个球队是个vertex,每场比赛是一个edge,整个NCAA赛季到了赛季末就是一个
directed graph,做个topological sort就能知道排名了。
可能的例外:
1)如果graph里边有环,就把整个环里包含的edge全部去掉
2)如果有topological sort上,并列的vectex,就把并列的vertex看成root,然后赢
过的球队看成这个root的children,把所有的children的children都算进来,算个总数
,数目大的排在前边,这就行了
S*******n
发帖数: 12762
26
【 以下文字转载自 Melody_In_The_Wind 俱乐部 】
发信人: Slytherin (小余|小则|小成), 信区: Melody_In_The_Wind
标 题: 潜伏 (10)Professor Gobeijinggo's Sorting Hat
发信站: BBS 未名空间站 (Mon Mar 28 21:32:19 2011, 美东)
第10章 PROFESSOR GOBEIJINGGO'S SORTING HAT
西北狼的讲话让气氛一下子活跃起来。正在这个时候,一个瘦高的人从台上走到了前台
,挥了挥WAND,一顶帽子突然出现在了台上。
众人立刻安静下来。这个人脸色严峻,一身黑袍,却正是北京教授,PROFESSOR OF THE
DENFENSE AGAINST THE DARK SEX。
"我念到名字的人都上台来,"北京不带感情地说道。
"这是怎么回事情?"余则成悄悄问到。瑟瑟和幽幽也是一脸的茫然。
"自从出现了LORD OF HH后,这里的规矩就严格了,要先进行性征审查的。"一个声音说
到。余则成回头一看,声音来自一个一头卷发的英俊小男生。
"我叫梅醒,"那个... 阅读全帖
H******e
发帖数: 4682
27
来自主题: Zhejiang版 - How to Sort XML Records in Visual Basic?
Hi, How to Sort XML Records in Visual Basic?
LZ编程为菜鸟级别, 请求immediate帮助, codes越详细越好, 可以酬谢上百包子。
Here I want to sort this xml file using the element .
My sample xml:
Code:




11/11/2003
Robust



11/10/2003
Robust1



12/11/2003
Robust3
阅读全帖
I*********t
发帖数: 5258
28
来自主题: Apple版 - Mac Terminal command "sort" -R option
Mac的sort虽然也是gnu sort,但是比较老。你可以用其它方法实现随机分选,比如
$ cat SortedFile.txt | perl -wnl -e '@f=<>; END{ foreach $i (reverse 0 .. $#
f) { $r=int rand ($i+1); @f[$i, $r]=@f[$r,$i] unless ($i==$r); } chomp @f;
foreach $line (@f){ print $line; }}'
这个应该是跨平台的
c****m
发帖数: 824
29
【 以下文字转载自 Linux 讨论区 】
发信人: ccccmm (猪喂曼玉), 信区: Linux
标 题: linux下如何sort一个大文件的内容?
发信站: BBS 未名空间站 (Wed Sep 17 00:38:28 2008)
有一个文件很大,有一个G。文件每行是一个数。如果用sort file
结果/tmp空间不够导致崩溃。有没有好办法?
r****o
发帖数: 1950
30
【 以下文字转载自 Programming 讨论区 】
发信人: roufoo (五经勤向窗前读), 信区: Programming
标 题: 嵌入式系统用什么sorting算法比较好?
发信站: BBS 未名空间站 (Tue Jul 12 03:13:52 2011, 美东)
quicksort通用的算法需要recursion,不太适合用于embedded system,因为有可能stack
overflow.
那大家都用的哪种sorting呢?
x********q
发帖数: 108
31
插入排序和bubble sort不一样的复杂度嘛。
又要快又省空间,理论上heap sort 似乎比较靠谱。
b****e
发帖数: 1275
32
来自主题: Database版 - sort
how can you sort data in a table? i don't believe they're
stored in a sequential way. when you retrievfe data using
sql, you can always specify sorting order
g****y
发帖数: 141
33
来自主题: Database版 - [转载] How to sort chinese data?
【 以下文字转载自 Programming 讨论区,原文如下 】
发信人: gjbaby (北京知青), 信区: Programming
标 题: How to sort chinese data?
发信站: The unknown SPACE (Wed May 29 11:14:30 2002) WWW-POST
for example,in Customers table,I got a list of chinese customers(in Chinese),
how sould I sort them
1)based on Bi3 Hua4(is it possible?)
2)based on Pinyin after translation
Now I got another table "Orders",how can I joinCustomers with Orders based on
the customer name?
m**********e
发帖数: 19
34
来自主题: DotNet版 - C#里有sort多维数组的东东么?
我查来查去,Array.Sort只支持一维数组,至多是两个一维数组.
如果我的sort需要用到primary key 和 secondary key, 好象就没有办法了.
s***y
发帖数: 4
35
来自主题: Java版 - JTable column sorting problem.
Hi! I am using Comparator to do column sorting for a JTable. It works
good with appletviewer. When I am using IE, it complains :
java.lang.IncompatibleClassChangeError
below is my code for Comparator interface:
I guess it is some thing wrong with Collection.sort()
//*****************************************************************
class ColComparator implements Comparator {

protected int m_sortCol;
protected boolean m_sortAsc;
public ColC
a*****i
发帖数: 4391
36
【 以下文字转载自 Programming 讨论区 】
【 原文由 ayanami 所发表 】
Supppose I have a HashMap wordmap with a String key, a integer value.
[Key=>value]
What is the easiest way to sort them based on value?
I looked at SortMap, but it only sorts based on key.
Thanks!
F****n
发帖数: 3271
37
What is a Hashtable? Hashtable use hashCode to index data, so you can not
"sort" the value, the only way you can do is to create another sorted list of
values.
g**********y
发帖数: 14569
38
来自主题: Java版 - Sort TreeMap by value?
怎么最简单地sort TreeMap? 我试了Comparator, 陷入chicken-and
-egg loop. 最后只好用个辅助List/Array来sort key. 有更简洁的办法吗?
h**j
发帖数: 2033
39
来自主题: Java版 - Sort TreeMap by value?
TreeMap本来就是sorted 为什么还要sort

and
k***s
发帖数: 277
40
来自主题: Linux版 - 一个关于sort的奇怪问题
sort中的-k来选择字段排序,但是我不知道如何解释下面的结果:
(不知道第二个命令是按什么字段来排序的!)
root@SlackFS:/mnt/fa# cat /etc/fstab | sort -k 1
/dev/cdrom /mnt/cdrom auto noauto,owner,ro 0 0
/dev/fd0 /mnt/floppy auto noauto,owner 0 0
/dev/hda1 / ext3 defaults 1 1
/dev/hdb5 /mnt/hdb5 auto noauto,owner 0 0
/dev/hdd6 /mnt/hdd6 auto noauto,owner 0 0
/dev/hdd7 /mnt/hdd7 auto noa
t*****g
发帖数: 5282
41
来自主题: Linux版 - linux sort 命令 求助
希望先对第一行按字典序排序,第二第三行按数字排序
sort -k1,1 -k2,3 -n -o sorted.txt tobesort.
结果是先按第二第三行排的, 然后再第一行排的了
b****j
发帖数: 78
42
来自主题: Linux版 - linux sort 命令 求助
试试这个:
sort -k 1,1 -k 2,3n -o sorted.txt tobesort
h*******c
发帖数: 248
43
来自主题: Linux版 - linux sort 命令 求助
到底是行还是列呀?我理解为列了。
我一般不用n,用g,忘了原因了,好像n有时候比较古怪。
cat tobedort|sort -k1,1 -k2,3g >sorted
c*******g
发帖数: 1996
44
sort是 linux 系统命令sort, 在cluster上就是用本地的scratch分区的
z****s
发帖数: 192
45
来自主题: Linux版 - 请教sort

抱歉理解错意思了。
这里麻烦的是逗号和数字粘在一起了,所以正确的应该是
sed 's/,/t/2;s/>/tt/2' |sort -k3,3n|sed 's/tt/>/;s/t/,/' your_txt_file
如果你的原文件有制表符(tab t),可以把上面的命令换为其他的字符。
"sort -t',' -k2.6n"只就第二个field的第六个character,就是“空,9,空”,排
序。只是对本题有效。
P*****f
发帖数: 2272
46
在sorted array中找一个数,binary search。
有个题是sorted array right/left shift 了k位(k unkown),问怎么查找。
这也是个老题了,我所知的solution是用modified binary search, 根据 left end,
right end 和middle point 的大小关系来判断下一次搜索的范围。不过今天突然想到
一个例子;
original array = { 1,2,3,3,3,3,3,3,3,3,3,3,,3,....3}. shift k位后成了
{3,3,3,3...3,1,2,3,3,3,3,3,3,3}.这个似乎二分查找无法搞定,只能线性搜索了吧。
讨论一下
h**o
发帖数: 548
47
来自主题: Programming版 - 几道面试题:memory, sort, 等
1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
是这个array size 较小.请问怎么sort?
2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
跟上.有人会作这题吗?或从那儿可以找到答案?
3. 如何判断是bigendian, little endian,
int i = 1;
if(*(char*)&i) return little;
else return big;
我一开始写成if((char)i) return little;他说我应用指针. 请问为何非用指针那?我
回来发现不用也对阿.
c*****t
发帖数: 1879
48
来自主题: Programming版 - 几道面试题:memory, sort, 等
回去复习一下 quicksort 的定义吧。你可以弄个 O (nlogn)不错,但是
那不一定是 quicksort 。不要指着 merge sort 或者 merge sort 的变种
说是 quicksort 。
P*****f
发帖数: 2272
49
来自主题: Programming版 - 几道面试题:memory, sort, 等
nth_element 一般实现是hoare select,average O(n).
这个和sort还不一样,partial_sort比这个就慢了
如果你是指worst case linear selection,其常系数也是相当的大。
radix O(n)没有问题,其实就是不是in place而已。
quick sort一般的角度来讲,average nlogn, worst n^2 也是没错的。
尽管你可以做些randomize,median of three之类的优化。

worst
其实就是根据nth_element可以O(n)
P*****f
发帖数: 2272
50
来自主题: Programming版 - 几道面试题:memory, sort, 等
这就是我说的worst cast linear selection, 但nth_element算法所有实现没有用这个的
1. 方法复杂不值得 2. 常数系数很大.
所以我说一般说quick sort worst case (n^2) 是可以的

终于找到了,introduction to algorithm 9.3,虽然bt了点,但是nth_element还是可
以O(n)
所以quicksort就可以O(nlogn),也不知道前面讲sorting的就咬定worst是n方
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)