数据结构之集合详解

￡神魔★判官ぃ 2022-02-23 00:08 285阅读 0赞

### 数据结构之集合详解 ###

*  集合（set）
 *   *  一个以二分搜索树为底层实现的集合
     *  一个以链表为底层实现的集合
     *  集合的时间复杂度分析
     *  唯一摩尔斯密码词 LeetCode804号问题
     *  有序集合和无序集合
     *  多重集合

# 集合（set） #

*  回忆我们之前实现的二分搜索树，它是不能存放重复元素的，它本身就是非常好的实现“集合”的底层数据结构

**`Set<E>`**

*  `void add(E)` 不能添加重复元素 典型应用：客户统计、词汇量统计
 *  `void remove(E)`
 *  `boolean contains(E)`
 *  `int getSize()`
 *  `boolean isEmpty()`

首先我们定义了一个set接口

public interface Set<E> { 
    
        void add(E e);
        boolean contains(E e);
        void remove(E e);
        int getSize();
        boolean isEmpty();
    }

## 一个以二分搜索树为底层实现的集合 ##

import java.util.ArrayList;
    
    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);
        }
    }

## 一个以链表为底层实现的集合 ##

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 void add(E e){ 
            if(!list.contains(e))
                list.addFirst(e);
        }
    
        @Override
        public boolean contains(E e){ 
            return list.contains(e);
        }
    
        @Override
        public void remove(E e){ 
            list.removeElement(e);
        }
    }

## 集合的时间复杂度分析 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]  
h为二分搜索树的高度，考虑特殊情况下高度h会等于n，使用平衡二叉树可以解决这个问题。

## 唯一摩尔斯密码词 LeetCode804号问题 ##

问题链接：[https://leetcode-cn.com/problems/unique-morse-code-words/][https_leetcode-cn.com_problems_unique-morse-code-words]

解答代码

import java.util.TreeSet;
    
    /** * Created by binzhang on 2019/4/5. */
    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']);
    
                set.add(res.toString());
            }
    
            return set.size();
        }
    }

## 有序集合和无序集合 ##

*  有序集合的元素具有顺序性 基于搜索树的实现
 *  无序集合中的元素没有顺序性 基于哈希表的实现（比搜索树更快）

## 多重集合 ##

*  集合中的元素可以重复

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20220223/cc11ee92496b46079c5d457ad8080206.png
[https_leetcode-cn.com_problems_unique-morse-code-words]: https://leetcode-cn.com/problems/unique-morse-code-words/