上节课学习了二分搜索树这样一种有序数据结构 ，本节课将借助二分搜索树来实现更高级的数据结构--集合与映射。
1. 集合
1.1 基于二分搜索树的集合实现
集合的主要特点是不能盛放重复元素，在实际生活中，应用也很广泛：
- 公司客户统计
- 书籍词汇量统计
上一节实现的二分搜索树不能添加相同的元素，是非常好的实现集合的底层数据结构。要实现集合，首先需要定义如下通用型集合接口：
public interface Set<E> {
// 1. 添加元素
public void add(E e);
// 2. 删除元素
public void remove(E e);
// 3. 判断是否为空
public boolean isEmpty();
// 4. 查看集合内元素个数
public int getSize();
// 5. 判断是否包含某元素
public boolean contains(E e);
}
然后使用上一节创建的二分搜索树来实现该接口：
import java.util.Comparator;
public class BSTSet<E extends Comparable<E>> implements Set<E> {
private BST<E> data;
public BSTSet() {
data = new BST<>();
}
@Override
public int getSize() {
return data.getSize();
}
@Override
public boolean isEmpty() {
return data.isEmpty();
}
@Override
public boolean contains(E e) {
return data.contains(e);
}
@Override
public void add(E e) {
data.addElement(e);
}
@Override
public void remove(E e) {
data.removeElement(e);
}
}
下面测试上述实现，编写测试函数，计算《傲慢与偏见》的词汇量，这里需要借助文件读取，首先实现文字的切割：
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Locale;
import java.io.File;
import java.io.BufferedInputStream;
import java.io.IOException;
// 文件相关操作
public class FileOperation {
// 读取文件名称为filename中的内容，并将其中包含的所有词语放进words中
public static boolean readFile(String filename, ArrayList<String> words){
if (filename == null || words == null){
System.out.println("filename is null or words is null");
return false;
}
// 文件读取
Scanner scanner;
try {
File file = new File(filename);
if(file.exists()){
FileInputStream fis = new FileInputStream(file);
scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
scanner.useLocale(Locale.ENGLISH);
}
else
return false;
}
catch(IOException ioe){
System.out.println("Cannot open " + filename);
return false;
}
// 简单分词
// 这个分词方式相对简陋, 没有考虑很多文本处理中的特殊问题
// 在这里只做demo展示用
if (scanner.hasNextLine()) {
String contents = scanner.useDelimiter("\\A").next();
int start = firstCharacterIndex(contents, 0);
for (int i = start + 1; i <= contents.length(); )
if (i == contents.length() || !Character.isLetter(contents.charAt(i))) {
String word = contents.substring(start, i).toLowerCase();
words.add(word);
start = firstCharacterIndex(contents, i);
i = start + 1;
} else
i++;
}
return true;
}
// 寻找字符串s中，从start的位置开始的第一个字母字符的位置
private static int firstCharacterIndex(String s, int start){
for( int i = start ; i < s.length() ; i ++ )
if( Character.isLetter(s.charAt(i)) )
return i;
return s.length();
}
}
测试函数：
public static void main(String[] args) {
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
System.out.println("Total words:"+words.size()); // 125901
BSTSet<String> bst = new BSTSet<>();
for(String word:words) {
bst.add(word);
}
System.out.println("Total different words: "+bst.getSize()); // 6530
}
else {
throw new IllegalArgumentException("Read failed");
}
}
可以看到，完成二分搜索树的增删逻辑之后，借助二分搜索树实现集合是非常简单的，下面考虑用链表实现集合。
1.2 基于链表的集合实现
基于之前构造的链表结构，也可以实现集合功能，只不过在添加元素时，需要先判断链表中是否已包含该元素，另外，链表集合中的泛型无需实现比较器：
import java.util.ArrayList;
public class LinkedListSet<E> implements Set<E> {
private LinkedList<E> list;
public LinkedListSet() {
list = new LinkedList<>();
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public boolean contains(E e) {
return list.contains(e);
}
@Override
public void add(E e) {
// 加一句判断，若列表中已包含元素，则不添加元素
if(!list.contains(e))
list.addFirst(e);
}
@Override
public void remove(E e) {
list.removeElement(e);
}
}
可以采用相同的测试函数来验证上述实现的有效性：
public static void main(String[] args) {
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
System.out.println("Total words:"+words.size()); // 125901
LinkedListSet<String> list = new LinkedListSet<>();
for(String word:words) {
list.add(word);
}
System.out.println("Total different words: "+list.getSize()); // 6530
}
else {
throw new IllegalArgumentException("Read failed");
}
}
运行时可以很明显感觉到将链表作为底层结构，耗时要比二分搜索树长很多。
1.3 时间复杂度分析
对于底层结构是链表的集合，其时间复杂度与链表的时间复杂度相关：
- 增(add)：链表本身添加操作的时间复杂度为O(1)，然而为实现集合元素不能重复的特性，添加元素时需要先遍历一遍链表，判断是否包含待添加元素，因此时间复杂度为O(n)
- 删(remove)：链表的删除操作需要找到待删除元素的前一节点，因此时间复杂度为O(n)
- 查(contains)： 需要遍历链表所有元素，复杂度为O(n)
下面分析二分搜索树的时间复杂度，二分搜索树本质上是一种顺序结构，增删查操作与二分搜索树的深度h有关：
image.png
考虑二分搜索树中节点个数n与深度h的关系：
- 对于一个满二叉树，除了叶子节点，每个节点都有两个孩子
image.png
可以看到，第层有
个节点，第
个节点，第
个节点，...，第
层有
个节点，因此对于满二叉树，
增删查的时间复杂度为
- 上面满二叉树是一种平均情况，对于极端的情况，二分搜索树有可能退化成链表，此时时间复杂度为
image.png
下面的测试函数用来简单测试链表集合类与二分搜索树集合类的效率：
public static double testSet(Set<String> set,String filename) {
long startTime = System.nanoTime();
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile(filename, words)) {
System.out.println("Total words:"+words.size());
for(String word:words) {
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) {
String filename = "pride-and-prejudice.txt";
BSTSet<String> bst = new BSTSet<String>();
double time1 = testSet(bst,filename);
System.out.println("BST set:"+time1+"s"); // 0.3
System.out.println();
LinkedListSet<String> linkedListSet = new LinkedListSet<>();
double time2 = testSet(linkedListSet, filename);
System.out.println("LinkedList set:"+time2+"s"); // 4.0355
}
2. leetcode中与集合有关的问题
804
国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。
所有26个英文字母对应的摩尔斯密码表如下：
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，"cab" 可以写成 "-.-..--..."，(即 "-.-." + "-..." + ".-"字符串的结合)。我们将这样一个连接过程称作单词翻译。不同的单词有可能被翻译为相同的摩尔斯密码，要求返回单词列表中不同摩尔斯密码的数量。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-morse-code-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
使用集合很容易解答该题，遍历单词列表，将每个单词的翻译结果放入一个集合中，由于集合不能存放相同的元素，因此，遍历完单词列表后，集合中元素的数量即为不同摩尔斯密码的数量。
-
应用Java集成的TreeSet类
import java.util.TreeSet; // leetcode 804 public class Solution { public int uniqueMorseRepresentations(String[] words) { String[] codes = {".-","-...","-.-.","-..",".","..-.", "--.","....","..",".---","-.-",".-..","--","-.", "---",".--.","--.-",".-.","...","-","..-","...-", ".--","-..-","-.--","--.."}; TreeSet<String> treeSet = new TreeSet<>(); for(String word:words) { StringBuilder res = new StringBuilder(); for(int i=0;i<word.length();i++) { // 将单词索引为i位置的字母翻译成摩尔斯密码，追加到翻译结果中 res.append(codes[word.charAt(i)-'a']); } treeSet.add(res.toString()); } return treeSet.size(); } } -
使用上一节中自己创建的Set类
import java.util.Comparator; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Solution { public int uniqueMorseRepresentations(String[] words) { String[] codes = {".-","-...","-.-.","-..",".","..-.", "--.","....","..",".---","-.-",".-..","--","-.", "---",".--.","--.-",".-.","...","-","..-","...-", ".--","-..-","-.--","--.."}; BSTSet<String> set = new BSTSet<>(); for(String word:words) { StringBuilder res = new StringBuilder(); for(int i=0;i<word.length();i++) { // 将单词索引为i位置的字母翻译成摩尔斯密码，追加到翻译结果中 res.append(codes[word.charAt(i)-'a']); } set.add(res.toString()); } return set.getSize(); } }
349
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
使用基于二分搜索树构造的集合类解决该问题：
class Solution { public int[] intersection(int[] nums1, int[] nums2) { BSTSet<Integer> bstSet = new BSTSet<>(); // 先将第一个数组中的元素添加到集合中 for(int num:nums1) { bstSet.add(num); } ArrayList<Integer> arr = new ArrayList<>(); for(int num:nums2) { // 遍历第二个数组中的所有元素，如果存在于集合中，则将该元素添加到数组列表中 // 同时从集合中移除该元素 if(bstSet.contains(num)) { arr.add(num); bstSet.remove(num); } } int[] res = new int[arr.size()]; for(int i = 0;i<arr.size();i++) { res[i] = arr.get(i); } return res; } }
3. 映射
映射（Map）是一种存储（键，值）数据对的数据结构（key,value），键在映射中是不可重复的，通过键（key）来寻找值（value）。映射在实际生活中同样具有广泛的应用：
- 字典中一个单词对应一个释义
- 名册中一个身份证号对应一个人
- 车辆管理中一个车牌对应一辆车
回顾之前介绍的链表和二分搜索树的结构：
// 链表中的节点结构 // 二分搜索树中的节点结构
class Node{ class Node{
E e; E e;
Node next; Node left;
} Node right;
}
很容易用这样的结构来实现映射机制，只需在节点中存储一对数据即可：
// 存储键值对的链表 // 存储键值对的二分搜索树
class Node{ class Node{
K key; K key;
V value; V value;
Node next; Node left;
} Node right;
}
一个Map应该包含如下基本接口：
public interface Map<K,V> {
// 1. 获取map中键值对个数
public int getSize();
// 2. 判断map是否为空
public boolean isEmpty();
// 3. 添加键值对
public void add(K key,V value);
// 4. 删除key对应的键值对，返回value
public V remove(K key);
// 5. 更新key对应的value
public void set(K key,V value);
// 6. 查询key对应的值
public V get(K key);
// 7. 判断是否包含指定的key
public boolean contains(K key);
}
3.1 使用链表实现Map
-
首先使用链表来实现Map，对链表节点结构进行修改，注意增加泛型支持：
public class LinkedListMap<K,V> implements Map<K,V> { // 私有结点类，存储键值对 private class Node{ private K key; private V value; private Node next; public Node(K key, V value, Node next) { this.key = key; this.value = value; this.next = next; } public Node(K key,V value){ this(key,value,null); } public Node() { this(null,null,null); } @Override public String toString() { return "Key: "+key.toString()+"Value:"+value.toString(); } } private Node dummyHead; private int size; } -
简单函数的实现
// 1. 获取map中键值对个数 public int getSize(){ return size; } // 2. 判断map是否为空 public boolean isEmpty() { return size == 0; } // 私有成员函数，根据key找到所在节点 private Node getNode(K key) { Node cur = dummyHead.next; while(cur!=null) { if(cur.key.equals(key)) { return cur; } cur = cur.next; } return null; }-
根据键查询
// 6. 判断是否包含指定的key @Override public boolean contains(K key) { Node node = getNode(key); return node != null; } // 7. 查询key对应的值 @Override public V get(K key) { Node node = getNode(key); return node.value; }
-
-
更新/修改
// 5. 更新key对应的value @Override public void set(K key, V value) { Node node = getNode(key); if(node!=null) { node.value = value; Node preNode = dummyHead.next; while(preNode.next!=null) { // 找到待更新结点的前一结点 if(preNode.next.key.equals(key)) { node.next = preNode.next.next; preNode.next = node; return; } preNode = preNode.next; } } // node.value = value; // 需事先判断Map中是否存在该键 } -
添加元素
// 3. 添加新的键值对 @Override public void add(K key, V value) { if(contains(key)) { // 如果已包含该键，更新该键对应的值 set(key,value); } else { // 如果不包含该键，添加到链表头 Node node = new Node(key,value); node.next = dummyHead.next; dummyHead.next = node; size++; } } -
删除元素
// 4. 删除key对应的键值对，返回value @Override public V remove(K key) { Node pre = dummyHead; Node delNode = new Node(); // 从虚拟头节点出发，找到待删除元素的前一节点 while(pre.next!=null) { if(pre.next.key.equals(key)) break; pre = pre.next; } // 如果找到的前一节点不是最后一个元素，则执行删除操作 if(pre.next!=null) { delNode = pre.next; pre.next = delNode.next; delNode.next = null; size --; } return delNode.value; }
3.2 leetcode中与Map相关的问题
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
利用基于链表构造的映射类来解决问题
public class Solution { public static int[] intersect(int[] nums1, int[] nums2) { LinkedListMap<Integer,Integer> linkedListMap = new LinkedListMap<Integer,Integer>(); // 遍历第一个数组中的元素，将元素及其对应出现的次数存入映射中 for(int num:nums1) { // 如果是之前添加过的元素，将元素出现的次数+1 if(linkedListMap.contains(num)) { linkedListMap.set(num, linkedListMap.get(num)+1); } // 如果之前没有添加过，以出现次数为1添加进映射中 else linkedListMap.add(num, 1); } ArrayList<Integer> arr = new ArrayList<>(); for(int num:nums2) { // 遍历第二个数组中的元素，如果包含在映射中，加入数组 列表中 if(linkedListMap.contains(num)) { // 如果该元素的次数大于1，加入数组列表，同时将出现次数减1 if(linkedListMap.get(num)>=1) { arr.add(num); linkedListMap.set(num, linkedListMap.get(num)-1); } // 如果该元素次数是0，则将其从映射中移除 else linkedListMap.remove(num); } } int[] res = new int[arr.size()]; for(int i = 0;i<arr.size();i++) { res[i] = arr.get(i); } return res; } }
3.3 使用二分搜索树实现Map
-
支持泛型的二分搜索树基本结构，注意键的可比较性
public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> { // 私有结点类 private class Node{ private K key; private V value; private Node left,right; public Node(K key, V value) { this.key = key; this.value = value; left = null; right = null; } @Override public String toString() { return "Key: "+key.toString()+"Value:"+value.toString(); } } 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); } // 私有添加方法，递归向以node为根结点的二分搜索树中添加键值对 // 返回插入新结点后二分搜索树的根 private Node add(Node node,K key,V value) { if(node==null) { node = new Node(key,value); size++; return node; } if(node.key.compareTo(key)>0) { node.left = add(node.left,key,value); } else if(node.key.compareTo(key)<0) { node.right = add(node.right,key,value); } else { // node.key.compareTo(key)==0 // 如果已存在该元素，做更新操作 node.value = value; } return node; } -
查询操作
// 返回以node为根节点的二分搜索树中，key所在的节点 private Node getNode(Node node,K key) { if(node==null) { return null; } if(node.key.compareTo(key)>0) { return getNode(node.left,key); } else if(node.key.compareTo(key)<0) { return getNode(node.right,key); } else { // node.key.compareTo(key)==0 return node; } } @Override public boolean contains(K key) { return getNode(root,key)!=null; } @Override public V get(K key) { Node node = getNode(root,key); return (node == null)?null:node.value; } // 返回以node为根的二分搜索树的最小值所在的节点 private Node minimize(Node node) { if(node.left==null) { return node; } return minimize(node.left); } -
修改/更新
@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; } -
删除
// 删除掉以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的节点 @Override public V remove(K key) { Node node = getNode(root,key); if(node!=null) { root = remove(root,key); } return node.value; } // 删除掉以node为根的二分搜索树中键为key的结点 // 返回删除节点后新的二分搜索树的根 private Node remove(Node node,K key) { if(node==null) { return null; } if(node.key.compareTo(key)>0) { node.left = remove(node.left,key); return node; } else if(node.key.compareTo(key)<0) { node.right = remove(node.right,key); return node; } else { // node.key.compareTo(key)==0 // 待删除结点右子树为空的情况 if(node.right==null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } // 待删除结点左子树为空的情况 if(node.left==null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } // 待删除节点左右子树均不为空的情况 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimize(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } }
3.4 两种底层实现的比较
import java.util.ArrayList;
public class Main {
private static double testMap(Map<String, Integer> map, String filename){
long startTime = System.nanoTime();
System.out.println(filename);
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile(filename, words)) {
System.out.println("Total words: " + words.size());
for (String word : words){
if(map.contains(word))
map.set(word, map.get(word) + 1);
else
map.add(word, 1);
}
System.out.println("Total different words: " + map.getSize());
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"); // 0.1520 s
System.out.println();
LinkedListMap<String, Integer> linkedListMap = new LinkedListMap<>();
double time2 = testMap(linkedListMap, filename);
System.out.println("Linked List Map: " + time2 + " s"); // 9.7194 s
}
}
4. 总结
本节课主要学习了集合与映射两种高级数据结构，分别以链表和二分搜索树为底层结构实现了这两种数据结构，并对存取效率进行了比较，存取效率与底层实现结构相关，以二分搜索树为底层结构的数据存取效率更高，这是因为二分搜索树的存取时间复杂度为，远小于链表的时间复杂度
。集合与映射在实际生活中的应用非常广泛，可以用来实现很多复杂任务。
