深圳 SEO 网站建设 哪里学,大庆建设中等职业技术学校网站,小城镇建设网站并阐述观点,石河子建设局网站1.哈希表的介绍
在哈希表中插入、删除或查找一个元素都只需要O(1)的时间#xff0c;因此经常被用来优化时间效率。
在Java中#xff0c;哈希表有两个对应的类型#xff0c;即HashSet和HashMap。
2.HashSet的应用
若每个元素都只有一个值#xff0c;则用HashSet#xf…1.哈希表的介绍
在哈希表中插入、删除或查找一个元素都只需要O(1)的时间因此经常被用来优化时间效率。
在Java中哈希表有两个对应的类型即HashSet和HashMap。
2.HashSet的应用
若每个元素都只有一个值则用HashSet如HashSet在图搜索时经常用来存储已经搜索过的节点。 以下为HashSet的常用函数
函数功能add添加一个元素contains判断是否包含一个元素remove删除一个元素size返回元素的数目
3.HashMap的应用
若每个元素都存在一个值到另外一个值的映射那么就用HashMap。 以下为HashMap的常用函数
函数功能containsKey判断HashMap中是否包括某个键get返回键对应的值否则nullgetOrDefault返回键对应的值否则返回输入的默认值put添加一组映射否则修改键对应的值putIfAbsent当键不存在时添加一组映射remove删除某个键replace修改某个键对应的值size返回映射数目
可以基于数组实现哈希表。
4.题目
面试30-插入、删除和随机访问都是O(1)的容器 解题思路 需要结合哈希表和数组的特性来设计数据容器。 采用长度可变的数组
ArrayList list new ArrayList();其中删除操作若考虑O(1)的时间复杂度因为不能保证删除的元素总在末尾所以将末尾的元素与要删除的元素换位置单方面交换–看代码然后删除末尾的元素注意都是从0开始。 提交的代码
class RandomizedSet {HashMapInteger,Integer map;//定义哈希表ArrayListInteger nums;//定义长度可变的数组//初始化public RandomizedSet(){mapnew HashMap();numsnew ArrayList();}//插入public boolean insert(int val){if(map.containsKey(val)){return false;}map.put(val,nums.size());nums.add(val);return true;}//删除public boolean remove(int val){if(!map.containsKey(val)){return false;}int locmap.get(val);map.put(nums.get(nums.size()-1),loc);//数组中最后一个元素放在要删除的位置map.remove(val);//map中删除val对应的键值对nums.set(loc,nums.get(nums.size()-1));//数组中最后一个元素放在要删除的位置nums.remove(nums.size()-1);return true;}//返回一个随机数public int getRandom(){Random randomnew Random();int rrandom.nextInt(nums.size());//随机生成0-nums.size()-1中的数字return nums.get(r);}
}ArrayList的用法
