d**********x
发帖数: 4083 | 1 那题目貌似就没卡复杂度。。。枉我昨天下班后还捏着鼻子写了个treap。。。结果证
明是输出格式错了，只过了两三个case的可以考虑检查一下输出格式
思路大致就是用order statistics tree。每次查询都是O(logn)。手写最大问题在于没
法定制容器的行为。。。
好吧，然后想了一下，如果用两个heap加一个map的话也是可以的，因为只是查询
median，没有要求随机查询kth元素，所以还是写复杂了
附上代码，treap是个随机平衡树，可以拿去用。
#include
#include
#include
#include
using namespace std;
template
class Treap {
public:
class Node {
public:
Node(const T& value)
: value_(value),
left_(NULL),
right_(NULL),... 阅读全帖 |
|
f*****d
发帖数: 36 | 2 1. Given a sorted dictionary of an alien language, find order of characters
2. discuss deeper into java arrayList and linkedList
How to create one chunkList have both of their advantage? My idea is to
implement it with a linkedlist but each node is an arrayList of adjusted
capacity.
when to use which one
how does java implement arrayList?
3. lunch interview
talking about current and past projects, which is the hardest one you have
ever met and some common behavior questions
4. design problem
add... 阅读全帖 |
|
|
l***i
发帖数: 1309 | 4 multiway merge is not hard, if you know AVL tree or treap, you could get
away with 2-3-4 tree or Red-black tree as they do similar things. |
|
|
e********3
发帖数: 229 | 6 这个treap如何应用到这道题上?
比如:
名字 call times
abc 50
abcd 100
abd 200
怎么通过call times在trie中进行排序? |
|
