From:
Design a data structure that offers the following operations in O(1) time:
- insert
- remove
- contains
- get random element
Solution:
Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.
- insert(value): append the value to array and let i be it's index in A. Set H[value]=i.
- remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
- contains(value): return H.contains(value)
- getRandomElement(): let r=random(current size of A). return A[r].
since the array needs to auto-increase in size, it's going to be amortize O(1) to add an element, but I guess that's OK.
public class ConstantRandomGet<E> { private Map<E, Integer> map = new HashMap<>(); private List<E> list = new ArrayList<>(); private Random random = new Random(); public void insert(E e) { map.put(e, list.size()); list.add(e); } public boolean remove(E e) { if(!map.containsKey(e)) return false; int i = map.get(e); int last = list.size()-1; E lastE = list.remove(last); map.put(lastE, i); list.set(i, lastE); return true; } public boolean contains(E e) { return map.containsKey(e); } public E getRandomElement() { int size = list.size(); if(size == 0) return null; int index = random.nextInt(size); return list.get(index); } }
相关推荐
Domain chapters: These chapters discuss the specific methods used for different domains of data such as text data, time-series data, sequence data, graph data, and spatial data. Application chapters: ...
With this book, you’ll gain a clear understanding of this discipline for discovering natural laws in the structure of data. Along the way, you’ll learn how to use the versatile R programming ...
Contains all important data structure and algorithms probl
關於python的data structure和algorithms,也就是數據結構和算法 Data structure and algorithms with python
Data Structure Data Structure Data Structure Data Structure Data Structure
Introduction to Data Science: A Python Approach to Concepts, Techniques and Applications By Laura Igual, Santi Seguí ... provides supplementary code resources and data at an associated website.
Combining knowledge with strategies, Data Structure Practice for Collegiate Programming Contests and Education presents the first comprehensive book on data structure in programming contests....
algorithm and Data Structure pdf
getdata软件适用于从图片中获取数据,是科研的必备软件。 想引用别人论文中的某个数据(曲线)图,但论文中没有这个图的数据,直接把图抓过来显得太逊了,希望提取出这个图中的数据信息生成矢量图; 希望从这个图中...
Practical Statistics for Data Scientists: 50 Essential Concepts by Peter Bruce, Andrew Bruce English | ISBN: 1491952962 | 2016 A key component of data science is statistics and machine learning, ...
Swift Data Structure and Algorithms by Erik Azar English | 18 Nov. 2016 | ISBN: 1785884506 | 286 Pages | AZW3/MOBI/EPUB/PDF (conv) | 22.7 MB Master the most common algorithms and data structures, and...
Data structure and algorithm analysis.Data structure and algorithm analysis
Data Structure and Algorithm(高清,英文原版)
伯克利教材 data structure in Java
Swift Data Structure and Algorithms
通过爬虫爬取非常著名的Data Structure Visualizations学习网页.离线保存网页.方便本地学习使用不用网络加载.快速体验数据结构可视化.
哈夫曼编码 065 图的深度优先遍利 066 图的广度优先遍利
Data structure of C++ .
Smart Grid using Big Data Analytics:A Random Matrix Theory Approach 大数据与智能电网理论与实践 big data and smart grid theory and practice
data structure chap 01