被pocket gems一道题绕了半天，杯具啊！

dxpppi 发表于 2015-11-3 14:19
还有一道sort color
要求sort的是objects with data field color(3 种)
follow up是有N个color怎么sort ...

看来这道题是二面必考啊...谢谢楼主啦！祝好运！

3-way partition 对于3色可以o(n) 搞定
N色也一样吧，不能new 那就只能老老实实交换排序啦......

clone graph你用的是map么……可以直接map指针吧……

sort colors难道是要你写bucket sort？O(n) 时间 O(n)空间

plich 发表于 2015-11-4 03:59
clone graph你用的是map么……可以直接map指针吧……

sort colors难道是要你写bucket sort？O(n) 时间 O ...

map指针是什么意思？map的key是original graph node，value是cloned graph node
sort color 3个颜色o(n) time o(1) space
k个颜色 o(n) time o(k) space  count sort呗。。。因为不许用constructor就先遍历一遍找出现过的object

补充一下吧，我这是二轮电面第二题。第一题是sort colored object（3 colors）follow up 1 : test cases 该怎么设置？ follow up 2： k个color怎么sort，object color 不可改，object 不能construct。

dxpppi 发表于 2015-11-4 04:04
补充一下吧，我这是二轮电面第二题。第一题是sort colored object（3 colors）follow up 1 : test cases 该 ...

那就使用基于比较的排序算法啦....quick sort的partition... 对于 3 color 只要一遍，O(n) time, O(1) space
k color,一样，worse O(kn)的时间，  在k远小于n的时候 可以认为是On ， 空间worse case是O(k)...

dxpppi 发表于 2015-11-4 04:02
map指针是什么意思？map的key是original graph node，value是cloned graph node
. .иsort color 3个颜色o(n) ...

. From 1point 3acres bbskey是original node的地址，value是cloned graph node的地址
用unordered_map<GraphNode*,GraphNode*> map;
来定义

O(n)空间是我想到了一个小的变形……那个题里面给的是一堆object，然后每个object都有一种method “get_catagory()”。要求按照catagory排序，且要保持相对顺序