|
[回复]
[修改] [删除]
[返回版面]
|
1 |
作者: admin, 讨论版: 算法集锦, 发表时间: 2014-02-27 14:36:48 PST
标题: O(1) data structure for insert/delete/contains/getRandom
关键字:
Design a data structure, where insert/delete/contains/getRandom are all O(1).
Answer: Hashtable + Array. Array stores the elements, hashtable stores the location of an element in the array: H(e) = i, where A[i] = e.
Insert(e): A[A.size ++] = e; H.insert(e);
Delete(e): i = H(e); H.erase(e); swap(A[i], A[A.size - 1]); A.size --;
Contains: return H.find(e);
getRandom: return A[rand(A.size)];
--
※ 来源: homecox.com [来自: 128.]
|
|
|
