这是悦乐书的第 298 次更新, 第 317 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 166 题(顺位题号是 705). 不使用任何内建的 hash 表库设计一个 hash 集合, 应包含以下功能:
add(value): 向哈希集合中插入一个值.
contains(value) : 返回哈希集合中是否存在这个值.
remove(value): 将给定值从哈希集合中删除. 如果哈希集合中没有这个值, 什么也不做.
例如:
- MyHashSet hashSet = new MyHashSet();
- hashSet.add(1);
- hashSet.add(2);
- hashSet.contains(1); // 返回 true
- hashSet.contains(3); // 返回 false (未找到)
- hashSet.add(2);
- hashSet.contains(2); // 返回 true
- hashSet.remove(2);
- hashSet.contains(2); // 返回 false (已经被删除)
注意:
所有的值都在 [1, 1000000]的范围内.
操作的总数目在 [1, 10000] 范围内.
不要使用内建的哈希集合库.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
利用数组, 哈希集合里所有值都在 [1, 1000000]的范围内, 用 key 当作数组下标, 如果存入数 key 就使 arrs[key]为 1, 用于判断哈希集合是否有该值.
- int arrs[]=new int[1000001];
- public MyHashSet() {
- }
- public void add(int key) {
- arrs[key]=1;
- }
- public void remove(int key) {
- arrs[key]=0;
- }
- public boolean contains(int key) {
- return arrs[key]==1;
- }
03 第二种解法
同第一种解法思路.
- boolean arrs[]=new boolean[1000001];
- public MyHashSet() {
- }
- public void add(int key) {
- arrs[key]=true;
- }
- public void remove(int key) {
- arrs[key]=false;
- }
- public boolean contains(int key) {
- return arrs[key]==true;
- }
04 第三种解法
使用 ArrayList 集合处理, 调用它提供的 API.
- private List<Integer> list = null;
- public MyHashSet() {
- list=new ArrayList<>();
- }
- public void add(int key) {
- list.add(key);
- }
- public void remove(int key) {
- for (int i = list.size() - 1; i>= 0; i--) {
- if (list.get(i) == key) {
- list.remove(i);
- }
- }
- }
- public boolean contains(int key) {
- return list.contains(key);
- }
05 小结
算法专题目前已日更超过四个月, 算法题文章 166 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/58baac31533e