我理解的数据结构（六）—— 集合和映射（Set And Map）

一、集合

1.典型应用场景

• 客户统计
• 词汇量统计

2.集合接口

public interface Set
    
      {    // 集合不存放相同元素    void add(E e);    // 删除元素    void remove(E e);    // 是否包含某个元素    boolean contains(E e);    // 总元素个数    int getSize();    // 集合是否为空    boolean isEmpty();}
    

3.基于二分搜索树的集合

关于二分搜索树的底层实现，大家可以去看我的另一篇文章：

public class BSTSet
    
     > implements Set
     
       {    private BST
      
        bst;    public BSTSet() {        bst = new BST<>();    }    @Override    public void add(E e) {        bst.add(e);    }    @Override    public void remove(E e) {        bst.remove(e);    }    @Override    public boolean contains(E e) {        return bst.contains(e);    }    @Override    public int getSize() {        return bst.getSize();    }    @Override    public boolean isEmpty() {        return bst.isEmpty();    }}
      
     
    

4.基于链表的集合

关于链表的底层实现，大家可以去看我的另一篇文章：

public class LinkedListSet
    
      implements Set
     
       {    private LinkedList
      
        list;    public LinkedListSet() {        list = new LinkedList<>();    }    @Override    public void add(E e) {        if (!list.contains(e)) {            list.addFirst(e);        }    }    @Override    public void remove(E e) {        list.removeElement(e);    }    @Override    public int getSize() {        return list.getSize();    }    @Override    public boolean contains(E e) {        return list.contains(e);    }    @Override    public boolean isEmpty() {        return list.isEmpty();    }}
      
     
    

5.BSTSet和LinkedListSet复杂度分析

\	LinkedListSet	BSTSet
add	O(n)	O(h)
contains	O(n)	O(h)
remove	O(n)	O(h)

注：

h为二分搜索树的高度，

n和

h是什么关系呢？

假设二分搜索树是一颗满树：

那么：n = 2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1即：h = log2(n + 1)因为这是我们假设的一种情况，真实情况种可能二分搜索树并不是一颗满树，所以这是一个平均复杂度，又在复杂度分析中可以不去考虑log的底，所以LinkedListSet和BSTSet的复杂度如下：

\	LinkedListSet	BSTSet
add	O(n)	O(logn) 平均
contains	O(n)	O(logn) 平均
remove	O(n)	O(logn) 平均

6.LeetCode中有关集合的问题

6.1 题目：6.2 描述：

国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。为了方便，所有26个英文字母对应摩尔斯密码表如下：[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，"cab" 可以写成 "-.-.-....-"，(即 "-.-." + "-..." + ".-"字符串的结合)。我们将这样一个连接过程称作单词翻译。返回我们可以获得所有词不同单词翻译的数量。

6.3例子：

例如:输入: words = ["gin", "zen", "gig", "msg"]输出: 2解释: 各单词翻译如下:"gin" -> "--...-.""zen" -> "--...-.""gig" -> "--...--.""msg" -> "--...--."共有 2 种不同翻译, "--...-." 和 "--...--.".

6.4解决代码如下：

import java.util.TreeSet;class Solution {    public int uniqueMorseRepresentations(String[] words) {        // 摩斯密码        String[] code = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};        TreeSet
    
      set = new TreeSet<>();        for (String word : words) {            // 每个单词的莫斯密码            StringBuilder res = new StringBuilder();            for (int i = 0; i < word.length(); i++) {                Character c = word.charAt(i);                res.append(code[c - 'a']);            }            set.add(res.toString());        }        return set.size();    }}
    

二、映射

1.映射基础：

• 存储（键、值）数据对的数据结构（key、value）
• 根据键（key），寻找值（value）

2.映射接口

public interface Map
    
      {    // 添加键值对    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 getSize();    // map是否为空    boolean isEmpty();}
    

3.基于链表的映射

public class LinkedListMap
    
      implements Map
     
       {    // 节点    private class Node {        // 存储key        public K key;        // 存储的value        public V value;        // 下一个节点        public Node next;        public Node(K key, V value, Node node) {            this.key = key;            this.value = value;            this.next = node;        }        public Node(K key) {            this(key, null, null);        }        public Node() {            this(null, null, null);        }        @Override        public String toString() {            return key.toString() + ':' + value.toString();        }    }    private int size;    private Node dummyHead;    public LinkedListMap() {        size = 0;        dummyHead = new Node();    }    @Override    public int getSize() {        return size;    }    @Override    public boolean isEmpty() {        return size == 0;    }    // 通过key获取对应的node节点    private Node getNode(K key) {        Node curNode = dummyHead.next;        while (curNode != null) {            if (curNode.key.equals(key)) {                return curNode;            } else {                curNode = curNode.next;            }        }        return 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;    }    @Override    public void add(K key, V value) {        Node node = getNode(key);        if (node != null) {            node.value = value;        } else {            dummyHead.next = new Node(key, value, dummyHead.next);            size++;        }    }    @Override    public void set(K key, V value) {        Node node = getNode(key);        if (node == null) {            throw new IllegalArgumentException(key + "is not exists");        } else {            node.value = value;        }    }    @Override    public V remove(K key) {        Node prev = dummyHead.next;        while (prev != null) {            if (prev.next.key.equals(key)) {                break;            } else {                prev = prev.next;            }        }        if (prev.next != null) {            Node delNode = prev.next;            prev.next = delNode.next;            delNode.next = null;            size--;            return delNode.value;        }        return null;    }}
     
    

4.基于二分搜索树的映射

public class BSTMap
    
     , V> implements Map
     
       {    // 节点    private class Node {        public K key;        public V value;        public Node left;        public Node right;        public Node(K key, V value) {            this.key = key;            this.value = value;            left = null;            right = null;        }    }    private int size;    private Node root;    public BSTMap() {        size = 0;        root = null;    }    @Override    public int getSize() {        return size;    }    @Override    public boolean isEmpty() {        return size == 0;    }    @Override    public void add(K key, V value) {        root = add(root, key, value);    }    // 向以node为根的二分搜索树中插入元素（key,value）    private Node add(Node node, K key, V value) {        if (node == null) {            size++;            return new Node(key, value);        }        if (node.key.compareTo(key) < 0) {            node.right = add(node.right, key, value);        } else if (node.key.compareTo(key) > 0) {            node.left = add(node.left, key, value);        } else { // node.key.compareTo(key) == 0            node.value = value;        }        return node;    }    // 返回以node为根节点的二分搜索树中指定key值的Node    private Node getNode(Node node, K key) {        if (node == null) {            return null;        }        if (node.key.compareTo(key) == 0) { // 找到指定的节点            return node;        } else if (node.key.compareTo(key) < 0) {            return getNode(node.right, key);        } else { // node.key.compareTo(key) > 0            return getNode(node.left, key);        }    }    @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;    }    @Override    public void set(K key, V value) {        Node node = getNode(root, key);        if (node == null) {            throw new IllegalArgumentException(key + "is not exists");        }        node.value = value;    }    @Override    public V remove(K key) {        Node node = getNode(root, key);        if (node != null) {            root = remove(root, key);            return node.value;        }        return null;    }    // 删除二分搜索树以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;    }    // 返回以node为根的二分搜索树的最小值的节点    private Node minimum(Node node) {        if (node.left == null) {            return node;        }        return minimum(node.left);    }    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 { // e == 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;                size--;                return leftNode;            }            // node的后继            Node successor = minimum(node.right);            // 把删除node.right的后继后的二叉树赋值给后继的right            successor.right = removeMin(node.right);            // 把node.left赋值给后继的left            successor.left = node.left;            node.left = node.right = null;            return successor;        }    }}
     
    

5.映射的复杂度分析

\	LinkedListMap	BSTMap
add	O(n)	O(logn) 平均
remove	O(n)	O(logn) 平均
set	O(n)	O(logn) 平均
get	O(n)	O(logn) 平均
contains	O(n)	O(logn) 平均

三、集合和映射的关系

从上面的代码可以看出，其实映射也是一个集合，只不过是携带了一个

value而已，本质和集合没有太大的区别。

四、两个LeetCode上集合和映射的问题

349. 两个数组的交集

题目地址：描述：给定两个数组，编写一个函数来计算它们的交集。例子：输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2]代码：

import java.util.ArrayList;import java.util.TreeSet;public class Solution {    // 349. 两个数组的交集    public int[] intersection(int[] nums1, int[] nums2) {        TreeSet
    
      set = new TreeSet<>();        for (int num : nums1) {            set.add(num);        }        ArrayList
     
       list = new ArrayList<>();        for (int num : nums2) {            if (set.contains(num)) {                list.add(num);                set.remove(num);            }        }        int[] arr = new int[list.size()];        for (int i = 0; i < list.size(); i++) {            arr[i] = list.get(i);        }        return arr;    }}
     
    

350. 两个数组的交集 II

题目地址：描述：给定两个数组，编写一个函数来计算它们的交集。例子：输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2,2]代码：

import java.util.ArrayList;import java.util.TreeMap;public class Solution {    // 350. 两个数组的交集 II    public int[] intersect(int[] nums1, int[] nums2) {        TreeMap
    
      map = new TreeMap<>();        for (int num : nums1) {            if (map.containsKey(num)) {                map.put(num, map.get(num) + 1);            } else {                map.put(num, 1);            }        }        ArrayList
     
       list = new ArrayList
      
       ();        for (int num : nums2) {            if (map.containsKey(num)) {                list.add(num);                int count = map.get(num);                map.put(num, --count);                if (count == 0) {                    map.remove(num);                }            }        }        int[] arr = new int[list.size()];        for (int i = 0; i < list.size(); i++) {            arr[i] = list.get(i);        }        return arr;    }}