本篇主要内容:集合及其应用
集合Set
数学上定义集合有最基本的三个性质:确定性、互异性和无序性。所谓确定性就是一个元素是否在这个集合中是确定的,互异性是一个集合中不能有相同的元素,无序性是打乱集合中元素的顺序集合还是这个集合。
在一般的数据结构教材中很少有讲解集合(Set)这种数据结构,不过理解集合这种数据结构是很必要的,它是一种高阶的数据结构,可以基于链表,二分搜索树等来实现。
在java语言中实现集合这种数据结构,首先写一个集合接口,集合可以由不同的方式实现:
'''Set.java'''
public interface Set<E> {
void add(E e);
void remove(E e);
boolean contains(E e);
int getSize();
boolean isEmpty();
}
基于链表的实现
java提供的有链表类,不过为了加深对一些操作的理解,这里我们使用的是自己写的链表类,它能实现增删查改的基本功能,而且支持泛型:
'''LinkedList.java'''
public class LinkedList<E> {
private class Node{
//链表节点是链表内部类而且私有,用户不需知道底层如何,屏蔽实现细节
public E e;
public Node next;
public Node(E e,Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
@Override
public String toString(){
return e.toString();
}
}
private Node dummyhead;
private int size;
public LinkedList(){
dummyhead = new Node(null,null);
size = 0;
}
//获取链表中元素的个数
public int getSize(){
return size;
}
//返回链表是否为空
public boolean isEmpty(){
return size == 0;
}
//在链表的index(0-based)位置添加新的元素e
//链表中不是常用操作,用作测试和练习
public void add(int index, E e){
if(index < 0||index > size)
throw new IllegalArgumentException("Add failed, illegal index");
else{
Node prev =dummyhead;
for(int i = 0;i<index;i++)
prev = prev.next;
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
//prev.next = new Node(e,prev.next);
size ++;
}
}
//链表头添加元素
public void addFirst(E e){
add(0,e);
}
//链表末尾添加元素e
public void addLast(E e){
add(size,e);
}
//链表中不是常用操作,用作测试和练习
//获得链表的第index个元素
public E get(int index){
if(index < 0||index > size)
throw new IllegalArgumentException("Add failed, illegal index");
Node cur = dummyhead.next;
for(int i=0;i<index;i++)
cur = cur.next;
return cur.e;
}
//获得链表的第一个元素
public E getFirst(){
return get(0);
}
//获得链表的最后一个元素
public E getLast(){
return get(size-1);
}
//修改index位置的元素为e
//测试练习用
public void set(int index,E e){
//链表中不是常用操作,用作测试和练习
if(index < 0||index > size)
throw new IllegalArgumentException("Add failed, illegal index");
Node cur = dummyhead.next;
for(int i=0;i<index;i++)
cur = cur.next;
cur.e = e;
}
//查找链表是否存在元素e
public boolean contains(E e){
Node cur = dummyhead.next;
while(cur != null){
if(cur.e.equals(e))
return true;
cur = cur.next;
}
return false;
}
//删除index位置的元素,不常用,做练习和测试
public E remove(int index){
if(index < 0||index > size)
throw new IllegalArgumentException("Add failed, illegal index");
Node prev = dummyhead;
for(int i=0;i<index;i++)
prev = prev.next;
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size --;
return retNode.e;
}
//删除链表第一个元素
public E removeFirst(){
return remove(0);
}
//删除链表最后一个元素
public E removeLast(){
return remove(size-1);
}
//从链表中删除元素e
public void removeElement(E e){
Node prev = dummyhead;
while(prev.next!=null){
if(prev.next.e.equals(e))
break;
prev = prev.next;
}
if(prev.next!=null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size --;
}
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
Node cur = dummyhead.next;
while(cur != null){
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
然后基于链表实现我们的集合,集合支持泛型:
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);
}
}
可以发现在实现链表后,集合中的增删查操作只需调用它底层的链表相应操作就行。
基于BST的实现
BST的实现我们在《算法之美》系列文章递归的妙用中实现过了,这里不再重复,下面给出基于BST的Set:
public class BSTSet<E extends Comparable<E>> implements Set<E> {
private BST<E> bst;
public BSTSet(){
bst = new BST<>();
}
@Override
public int getSize(){
return bst.size();
}
@Override
public boolean isEmpty(){
return bst.isEmpty();
}
@Override
public void add(E e){
bst.add(e);
}
@Override
public boolean contains(E e){
return bst.contains(e);
}
@Override
public void remove(E e){
bst.remove(e);
}
}
虽然两种方式都能实现Set这种数据结构,但是两者的性能存在巨大差异,基于链表实现的Set性能要远远低于基于BST实现的Set,这是为什么呢?这涉及到链表和BST的时间复杂度分析:
操作\方式 | 链表Set | BSTSet |
---|---|---|
增 | O(n) | O(h) |
删 | O(n) | O(h) |
查 | O(n) | O(h) |
对于我们实现的链表Set来说,不难得出它的增删查时间复杂度都是O(n),这里要说明的是本来链表的添加操作在头部时间复杂度仅为O(1),不过集合要求互异性,所以添加元素时还要检查该元素是否已经存在,故最终添加操作的时间复杂度是O(n)。而对于BSTSet,它的时间复杂度和BST的深度有关,最坏的情况下BST会退化为链表,时间复杂度也会是O(n),不过平均下来,BST的高度是,故BSTSet的平均时间复杂度是,这是远远优于O(n)的。如果Set是基于平衡二叉树来实现,则最坏情况复杂度也是,这实际上就是java中Set的实现方式。
集合的应用
文本词数统计
文本词数统计有很广泛的应用,比如词数统计可以用于书的难度分级,一本有10000个不同单词的书和一本有3000个不同单词的书显然不是一个难度级别。
现在我们就基于集合来实现一个txt英文小说词数统计的小程序。首先编写一个文件读取类,这个类用于做分词,将txt文本中英文单词提取出来并全部转为小写保存到String数组中:
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;
}
// 简单分词
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();
}
}
这只是一个简单的分词过程,全部转换为小写后单词不同就算不同。有学过自然语言处理的可以更加细化一下分词过程,比如将名词的单复数算为一个单词,动词的原型ing、ed、第三人称单数算作一个单词......不过这就比较麻烦了,本文不再进行这样的处理。接下来使用我们的集合对Little Prince这部童话的英文版进行词数统计:
'''Main.java'''
import java.util.ArrayList;
//BST比链表实现的集合更加高效
public class Main {
private static double testSet(Set<String> set,String filename){
long startTime = System.nanoTime();
System.out.println("Little Prince");
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 = "little-prince.txt";
LinkedListSet<String> linkedListSet = new LinkedListSet<>();
double time2 = testSet(linkedListSet,filename);
System.out.println(time2+"\n");
BSTSet<String> bstSet = new BSTSet<>();
double time1 = testSet(bstSet,filename);
System.out.println(time1+"\n");
}
}
在上面的代码中,我们用链表Set和BSTSet都进行了词数统计任务,并对它们的过程计时,运行结果如下:
词数统计可以看到两种方式都给出了正确的词数统计,而且BSTSet方式明显用时更少。
LeetCode804——唯一摩尔斯密码词
接下来用集合来解决一道LeetCode上的题目,题目描述如下:
LeetCode804-1 LeetCode804-2这里我们不再用自己的Set,而是用java中提供的TreeSet(底层是平衡二叉树,性能更好)来实现我们的Solution:
import java.util.TreeSet;
class Solution {
public int uniqueMorseRepresentations(String[] words) {
String[] codes = {".-","-...","-.-.","-..",".","..-.","--.",
"....","..",".---","-.-",".-..","--","-.","---",".--.",
"--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
TreeSet<String> set = new TreeSet<>();
for(String word:words){
StringBuilder res = new StringBuilder();
for(int i=0;i<word.length();i++)
res.append(codes[word.charAt(i)-'a']);//当前字符对应的摩斯码存入res
set.add(res.toString());
}
return set.size();
}
}
提交,获得通过!
网友评论