玩转数据结构——第六章：集合和映射
集合(Set)
什么是集合？
集合是承载元素的容器；
特点：每个元素只能存在一次
优点：去重
- 二分搜索树的添加操作add：不能盛放重复元素
- 是非常好的实现“集合”的底层数据结构
/**
* 集合的接口
*/
public interface Set<E> {
void add(E e);//添加 <——<不能添加重复元素
void remove(E e);//移除
int getSize();//获取大小
boolean isEmpty();//是否为空
boolean contains(E e);//是否包含元素
}典型应用：1.客户统计 2.词汇量统计
1-1基于二分搜索树实现集合Set
/**
* 基于BST二分搜索树实现的集合Set
*
* @param <E>
*/
public class BSTSet<E extends Comparable<E>> implements Set<E> {//元素E必须满足可比较的
private BST<E> bst;//基于BST类的对象
//构造函数
public BSTSet() {
bst = new BST<>();
}
//返回集合大小
@Override
public int getSize() {
return bst.size();
}
//返回集合是否为空
@Override
public boolean isEmpty() {
return bst.isEmpty();
}
//Set添加元素
@Override
public void add(E e) {
bst.add(e);
}
//是否包含元素
@Override
public boolean contains(E e) {
return bst.contain(e);
}
//移除元素
@Override
public void remove(E e) {
bst.remove(e);
}
}
测试：两本名著的词汇量 和不重复的词汇量
public static void main(String[] args) {
System.out.println("Pride and Prejudice");
//新建一个ArrayList存放单词
ArrayList<String> words1=new ArrayList<>();
//通过这个方法将书中所以单词存入word1中
FileOperation.readFile("pride-and-prejudice.txt",words1);
System.out.println("Total words : "+words1.size());
BSTSet<String> set1=new BSTSet<>();
//增强for循环，定一个字符串word去遍历words
//底层的话会把ArrayList words1中的值一个一个的赋值给word
for(String word:words1)
set1.add(word);//不添加重复元素
System.out.println("Total different words : "+set1.getSize());
System.out.println("-------------------");
System.out.println("Pride and Prejudice");
//新建一个ArrayList存放单词
ArrayList<String> words2=new ArrayList<>();
//通过这个方法将书中所以单词存入word1中
FileOperation.readFile("a-tale-of-two-cities.txt",words2);
System.out.println("Total words : "+words2.size());
BSTSet<String> set2=new BSTSet<>();
//增强for循环，定一个字符串word去遍历words
//底层的话会把ArrayList words1中的值一个一个的赋值给word
for(String word:words2)
set2.add(word);//不添加重复元素
System.out.println("Total different words : "+set2.getSize());
}
结果：
Pride and Prejudice
Total words : 125901
Total different words : 6530
-------------------
Pride and Prejudice
Total words : 141489
Total different words : 99441-2基于链表(LinkedList)的实现集合实现
- BST和LinkedList都属于动态数据结构
代码：
public class LinkedListSet<E> implements Set<E> {
/**
* 基于链表实现集合类
*/
private LinkedList<E> list;//创建一个链表对象
//构造函数
public LinkedListSet() {
list = new LinkedList<>();//初始化
}
//重写集合的方法
@Override
public int getSize() {
return list.getSize();
}
//集合是否为空
public boolean isEmpty() {
return list.isEmpty();
}
//是否包含元素e
public boolean contains(E e) {
return list.contains(e);
}
/**
* 添加元素
* Set中不能添加重复元素
* LinkedList可以添加重复元素
* 解决方式：先判断是否包含此元素
* 不包含再添加
*/
@Override
public void add(E e) {
if (!list.contains(e)) {
list.addFirst(e);
}
}
@Override
public void remove (E e){
list.removeElement(e);
}
}
测试：和上面用二分搜索的测试结果一样，不过时间比它的长(测试用例：将上面BSTSet改成LinkedListSet即可）
1-3.两种集合类的复杂度分析
测试两种集合类查找单词所用的时间
public class Main {
//创建一个测试方法 Set<String> set:他们可以是实现了该接口的LinkedListSet和BSTSet对象
private static double testSet(Set<String> set, String filename) {
//计算开始时间
long startTime = System.nanoTime();
System.out.println("Pride and Prejudice");
//新建一个ArrayList存放单词
ArrayList<String> words1 = new ArrayList<>();
//通过这个方法将书中所以单词存入word1中
FileOperation.readFile(filename, words1);
System.out.println("Total words : " + words1.size());
//增强for循环，定一个字符串word去遍历words
//底层的话会把ArrayList words1中的值一个一个的赋值给word
for (String word : words1)
set.add(word);//不添加重复元素
System.out.println("Total different words : " + set.getSize());
//计算结束时间
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;//纳秒为单位
}
public static void main(String[] args) {
//基于二分搜索的集合
BSTSet<String> bstSet = new BSTSet<>();
double time1 = testSet(bstSet, "pride-and-prejudice.txt");
System.out.println("BSTSet:" + time1 + "s");
System.out.println("————————————————————");
//基于链表实现的集合
LinkedListSet<String> linkedListSet = new LinkedListSet<>();
double time2 = testSet(linkedListSet, "pride-and-prejudice.txt");
System.out.println("linkedListSet:" + time2 + "s");
}
}结果：BSTSet的速度比LinkedListed的速度快
Pride and Prejudice
Total words : 125901
Total different words : 6530
BSTSet:0.263255132s
————————————————————
Pride and Prejudice
Total words : 125901
Total different words : 6530
linkedListSet:4.080751976s集合的时间复杂度分析：
| 集合操作 | LinkedListSet | BSTSet |
| 增add | O(n)，增之前查询一遍 |
(平均)是O(logn) (最差)O(n)： 二分搜索树可能退化成链表 h: 二分搜索树的深度 每一次操作都是一层 一层的往下找 |
| 查contains | O(n) | |
| 删remove | O(n)，删也要查询 |
logn和n的差距
| logn | n | logn和n的差距 | |
| n=16 | 4 | 16 | 相差4倍 |
| n=1024 | 10 | 1024 | 相差100倍 |
| n=100万 | 20 | 100万 | 相差5万倍 |
二分搜索树：
满二叉树的情况（每个节点都有左右节点，除了叶子节点）
| 层数 | 这层的节点数 | （0-h-1）h层，一共有多少个节点 |
| 0 | 1个节点 | 2^0+2^1+2^2+2^3+2^4...+2^(h-1= |
| 1 | 2个节点 | 等比数列： a1*(1-q^n)/(a1-q1) |
| 2 | 4个节点 |
|
| 3 | 8个节点 | |
| 4 | 16个节点 | 底数是多少不影响它是log级别的 |
| h-1 | 2^(h-1)个节点 | 相当于O(1/2n)=O(n) |
7-4.LeetCode中的集合问题和更多集合相关的问题
804.唯一的摩斯密码词
国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。
为了方便，所有26个英文字母对应摩尔斯密码表如下：
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，"cab" 可以写成 "-.-.-....-"，(即 "-.-." + "-..." + ".-"字符串的结合)。我们将这样一个连接过程称作单词翻译。
返回我们可以获得所有词不同单词翻译的数量。
例如:
输入: words = ["gin", "zen", "gig", "msg"]
输出: 2
解释:
各单词翻译如下:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
共有 2 种不同翻译, "--...-." 和 "--...--.".
注意:- 单词列表
words的长度不会超过100。 - 每个单词
words[i]的长度范围为[1, 12]。 - 每个单词
words[i]只包含小写字母。
思路：
将摩斯密码转换表用字符串数组存起来
然后遍历输入的字符串组，拿到当前字符串(chatAt())的索引(根据索引才能利用转化表)将其转换为摩斯密码并拼接到res中，
并用一个集合数据结构(TreeSet)来保存add(res.toString())进去实现去重功能
最后返回这个集合的元素个数即可
public class Solution {
public static int uniqueMorseRepresentations(String[] words) {
String[] codes = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...",
"-", "..-", "...-", ".--", "-..-", "-.--", "--.."};
/**
* TreeSet基于红黑树实现的集合
*/
//新建TreeSet一个对象
TreeSet<String> set = new TreeSet<>();
//遍历word数组
for (String word : words) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < word.length(); i++) {
word.charAt(i);//获得当前字符
//获得在code是的索引,将转换的Morse码拼接到res中
res.append(codes[word.charAt(i) - 'a']);//a-a=0,b-a=1
}
set.add(res.toString());//将res里面的字符串添加到set中，set会自动帮我们去重
System.out.println(res.toString());
}
return set.size();
}
测试：
public static void main(String[] args) {
String[] words = {"gin", "zen", "gig", "msg"};
System.out.println("字符串中的莫斯密码有：" + uniqueMorseRepresentations(words) + "种");
}结果:
--...-.
--...-.
--...--.
--...--.
字符串中的莫斯密码有：2两种有序集合和无序集合
有序集合：元素中具有顺序性<——<基于搜索树实现
无序集合：上一节链表实现的集合是无序的集合，元素没有顺序性<——<基于哈希表的实现
多重集合
- 集合中的元素可以重复
7.5映射Map(字典)
- 一一映射，在定义域中每一个值在值域都有一个值与他对应
- 存储(键，值)数据对的数据结构（Key，Value）
- 根据键(Key)，寻找值(Value)
定义Map的接口
public interface Map<K, V> {
//增
void add(K key, V value);
//删
V remove(K key);
//查
boolean contains(K key);
V get(K key);
//改
void set(K key, V value);
//获取字典大小
int getize();
boolean isEmpty();
}7.6基于链表实现映射类Map
整体结构：
获取映射大小和判空操作
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}辅助方法：通过key值查看是否包含这个节点，如果有返回这个节点
/**
* 辅助方法
* 通过key值返回这个节点
*
* @param key
* @return
*/
private Node getNode(K key) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.key.equals(key)) {
return cur;//返回找到这个节点
}
cur = cur.next;
}
return null;//找不到这个节点返回null
}查询操作
//看是否有这个数据
@Override
public boolean contains(K key) {
return getNode(key) != null;
}
//操作操作
@Override
public V get(K key) {
Node node = getNode(key);//找到这个节点
return node == null ? null : node.value;//如果这个节点为空则返回空，如果不为空返回这个元素
}添加操作
/**
* 添加操作
*
* @param key//key不能重复
* @param value
*/
@Override
public void add(K key, V value) {
Node node = getNode(key);//确认是否已经有这个数据
if (node == null) {
//它的next就等于当前dummyHead.next
dummyHead.next = new Node(key, value, dummyHead.next);
size++;
} else {//也可以做提醒添加重复的值，或者更新它的value
node.value = value;//更新
}
}更新操作
/**
* 更新操作
*/
@Override
public void set(K key, V newValue) {
Node node = getNode(key);//看是否有这个节点
if (node == null) {
throw new IllegalArgumentException(key + "does't exist！");
}
node.value = newValue;
}删除操作
/**
* 删除操作
*/
@Override
public V remove(K key) {
Node prev = dummyHead;
while (prev.next != null) {
if (prev.next.key.equals(key)) {
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.value;//返回这个删除元素的
}
prev = prev.next;
}
return null;//如果没有这个key
}测试：
/**
* 测试
*/
public static void main(String[] args) {
System.out.println("Pride and Prejudice");
ArrayList<String> words = new ArrayList<>();
if (FileOperation.readFile("pride-and-prejudice.txt", words)) {
System.out.println("Total words:" + words.size());
//key,value找出每个单词出现的频率
LinkedListMap<String, Integer> map = new LinkedListMap<>();
for (String word : words) {
if (map.contains(word)) {
//如果有这个单词，则通过get(key)找到这个value值并加1
map.set(word, map.get(word) + 1);
} else
//如果单词是第一次出现
map.add(word, 1);//频率初始值是1
}
System.out.println("Toal different words:" + map.getSize());
//查看pride单词出现的频率
System.out.println("Frequency of PRIDE:" + map.get("pride"));
System.out.println("Frequency of PREJUDICE:" + map.get("prejudice"));
}
}结果：
Pride and Prejudice
Total words:125901
Toal different words:6530
Frequency of PRIDE:53
Frequency of PREJUDICE:117.7基于二分搜索树实现映射类Map
定义节点内部类
//定义节点内部类
private class Node {
public K key;//键
public V value;//值
public Node left, right;//节点next
//节点的构造方法
public Node(K key, V value) {
this.key = key;//用户传进来的key赋值给当前节点的key
this.value = value;//用户传来的value当前节点的value
right = null;
left = null;
}
} 简单的初始化和获取map大小和判空的方法
private Node root;//根节点
private int size;
//构造函数
public BSTMap() {
root = null;
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}添加操作：
//向二分搜索树中添加新的元素(Key,Value)
@Override
public void add(K key, V value) {
root = add(root, key, value);
}
/**
* 二分搜索树：当前节点
* 大于其左子树的所有节点的值
* 小于其右子树的所有节点的值
*
* @param node
* @param key
* @return
*/
//向以node为根节点的二分搜索树插入元素(key,value),递归算法，//返回插入新节点后二分搜索树的根
private Node add(Node node, K key, V value) {
//1最基本问题的解决
if (node == null) {//还有一种是从空节点的二叉树中插入元素
size++;//记录元素个数
return new Node(key, value);
}
if (key.compareTo(node.key) < 0) {//当前指定的元素e小于node的值，则在左边插入
node.left = add(node.left, key, value);//调用递归
} else if (key.compareTo(node.key) > 0) {//当前指定的元素e大于node的值，则在右边插入
node.right = add(node.right, key, value);
} else//key.compareTo(node.key)==0
node.value = value;
return node;//返回插入新节点后二分搜索树的根
}辅助函数
//返回以node为根节点的二分搜索树中，Key所在的节点
private Node getNode(Node node, K key) {
if (node == null) {
return null;
}
if (key.compareTo(node.key) == 0) {//找到了
return node;
} else if (key.compareTo(node.key) < 0)
//递归继续去node的左子树中寻找
return getNode(node.left, key);
else//key.compareTo(node.key)>0
//递归继续去node的左子树中寻找
return getNode(node.right, key);
}更新、一些其他方法
@Override
public boolean contains(K key) {
return getNode(root, key) != null;//从根节点开始寻找这个key
}
//通过key返回value
@Override
public V get(K key) {
Node node = getNode(root, key);
return node == null ? null : node.value;
}
@Override
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null)//如果没有这个元素
throw new IllegalArgumentException(key + "doesn't exist!");
node.value = newValue;//更新value值
}删除操作：难点
// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node) {
if (node.left == null)
return node;
return minimum(node.left);
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
//从二分搜索树中删除键为key的节点
public V remove(K key) {
Node node = getNode(root, key);
if (node != null) {
root = remove(root, key);
return node.value;
}
return null;
}
//删除以node为根的二分搜索树中键为key的节点，递归算法
//返回删除节点后新的二分搜索树的根
private Node remove(Node node, K key) {
if (node == null)
return null;
if (key.compareTo(node.key) < 0) {//要删除的元素e比当前元素小
node.left = remove(node.left, key);
return node;
} else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
return node;
} else {//e.equals(node.e)
//待删除节点的左子树为空的情况
if (node.left == null) {
Node rightNode = node.right;//保存一下这个孩子的右子树
node.right = null;//右子树
size--;
return rightNode;
}
//待删除节点的右子树为空的情况
if (node.right == null) {
Node leftNode = node.left;
node.left = null;//让当前的node与二分搜索树脱离 满足node.left=node.right=null
size--;
return leftNode;
}
//待删除的节点左右子树均不为空
//找到比待删除节点到达的最小节点，即待删除节点的右节点的最小节点
//用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);//找到当前节点右子树最小的值
//successor为顶替待删除的节点(后继)
successor.right = removeMin(node.right);//将node.right的最小值给删除
successor.left = node.left;
node.left = node.right = null;//让当前node与二分搜索树脱离关系
return successor;
}
}测试结果：和用LinkedList实现的结果一样，但速度快多了
7.8映射的复杂度分析和更多映射相关的问题
基于二分搜索树和基于链表实现的映射的时间差异：
public class MainMap {
//创建一个测试方法 Set<String> set:他们可以是实现了该接口的LinkedListSet和BSTSet对象
private static double testMap(Map<String, Integer> map, String filename) {
//计算开始时间
long startTime = System.nanoTime();
System.out.println("Pride and Prejudice");
ArrayList<String> words = new ArrayList<>();
if (FileOperation.readFile(filename, words)) {
System.out.println("Total words:" + words.size());
//key,value找出每个单词出现的频率
for (String word : words) {
if (map.contains(word)) {
//如果有这个单词，则通过get(key)找到这个value值并加1
map.set(word, map.get(word) + 1);
} else
//如果单词是第一次出现
map.add(word, 1);//频率初始值是1
}
System.out.println("Toal different words:" + map.getSize());
//查看pride单词出现的频率
System.out.println("Frequency of PRIDE:" + map.get("pride"));
System.out.println("Frequency of PREJUDICE:" + map.get("prejudice"));
}
//计算结束时间
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;//纳秒为单位
}
public static void main(String[] args) {
String filename = "pride-and-prejudice.txt";
BSTMap<String, Integer> bstMap = new BSTMap<>();
double time1 = testMap(bstMap, filename);
System.out.println("BST Map: " + time1 + " s");
System.out.println("------------");
LinkedListMap<String, Integer> linkedListMap = new LinkedListMap<>();
double time2 = testMap(linkedListMap, filename);
System.out.println("LinkedList Map: " + time2 + " s");
}
}结果：
Pride and Prejudice
Total words:125901
Toal different words:6530
Frequency of PRIDE:53
Frequency of PREJUDICE:11
BST Map: 0.358648249 s
------------
Pride and Prejudice
Total words:125901
Toal different words:6530
Frequency of PRIDE:53
Frequency of PREJUDICE:11
LinkedList Map: 23.002140494 s时间复杂度分析：
有序映射和无序映射
有序映射中键具有顺序性的<——<基于搜索树实现
无序映射中键没有顺序性的 <——<基于哈希表实现
多重映射：键可以重复的
集合映射的关系
- 基于集合(Set<E>)的实现来实现映射(Map<K,V>)
重定义集合中的元素是<K,V>
重定义的数据对是以K键来进行比较的，而不去管value值
- 基于映射(Map<K,V>)实现来实现集合(Set<E>)更常见的方法
当我们有一个底层映射实现了
集合我们就可以理解成Map<K,V>中的V值为null的情况
对不管是什么K，它所对应的V都是空
当我们只考虑K的时候，整个Map，就是V的集合