集合set
集合的特点
集合中的元素都是不重复的，所以，我们就可以通过二分搜索树来设计集合这种数据结构。
集合的实现
网络异常，图片无法展示
|
通过二分搜索树实现set
public class BSTSet<E extends Comparable<E>> implements SetInterface<E>{ private BST<E> bst = null; public BSTSet() { bst = new BST(); } @Override public int getSize() { return bst.getSize(); } @Override public void add(E e) { bst.add(e); } @Override public void remove(E e) { bst.remove(e); } @Override public boolean isEmpty() { return bst.isEmpty(); } @Override public boolean contains(E e) { return bst.contains(e); } }
通过链表实现set
package com.zh.set13; import com.zh.linkedlist07.LinkedList; /** * @author zhanghao * @create 2022-05-29 14:48 */ public class LinkedListSet<E> implements SetInterface<E> { private LinkedList<E> list = null; public LinkedListSet() { list = new LinkedList<>(); } @Override public int getSize() { return list.getSize(); } @Override public void add(E e) { if(!list.contains(e)) { list.addFirst(e); // 首部添加，时间复杂度为o(1) } } @Override public void remove(E e) { list.removeElement(e); } @Override public boolean isEmpty() { return list.isEmpty(); } @Override public boolean contains(E e) { return list.contains(e); } }
复杂度分析
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
LeetCode相关习题
LeetCode 804
通过set存储的是不重复的值的特性。
import java.util.TreeSet; class Solution { public int uniqueMorseRepresentations(String[] words) { String[] chars = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}; TreeSet set = new TreeSet(); for(String word : words) { StringBuffer res = new StringBuffer(); for(int i = 0; i < word.length(); i++) { String code = chars[word.charAt(i) - 'a']; res.append(code); } set.add(res.toString()); } return set.size(); } }
映射Map
map特征
网络异常，图片无法展示
|
map的设计
网络异常，图片无法展示
|
网络异常，图片无法展示
|
通过链表实现Map
接口
public interface MapInterface<K, V> { void add(K key, V value); V remove(K key); void set(K key, V value); V get(K key); int getSize(); boolean contains(K key); boolean isEmpty(); }
map实现
public class LinkedListMap<K, V> implements MapInterface<K, V> { private class Node { public K key; public V value; public Node next; public Node(K key, V value, Node next) { this.next = next; this.key = key; this.value = value; } public Node(K key, V value) { this.key = key; this.value = value; } 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(); } private Node getNode(K key) { Node cur = dummyHead.next; // 当前是头节点 while(cur != null) { if(key.equals(cur.key)) { return cur; } cur = cur.next; } return null; } @Override public void add(K key, V value) { if(getNode(key) != null) return; // 如果添加相同的元素，那么将不做处理 // 创建一个新节点, 并将头结点作为该节点的下一个节点 Node node = new Node(key, value, dummyHead.next); // 将dummyHead指向改新节点 dummyHead.next = node; size++; } @Override public V remove(K key) { Node prev = dummyHead; while(prev.next != null) { if(key.equals(prev.next.key)) { // 查找到 Node cur = prev.next; prev.next = cur.next; cur.next = null; size--; return cur.value; } prev = prev.next; } return null; } @Override public void set(K key, V value) { Node cur = getNode(key); if(cur != null) { // 有就修改 cur.value = value; }else { // 没有就新增 add(key, value); } } @Override public V get(K key) { return getNode(key).value; } @Override public int getSize() { return size; } @Override public boolean contains(K key) { return getNode(key) != null; } @Override public boolean isEmpty() { return size == 0; } // toString方法 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("["); Node cur = dummyHead.next; while(cur != null) { res.append(cur); if(cur.next != null) { res.append(","); } cur = cur.next; } res.append("]"); return res.toString(); } }
通过二分搜索树实现map
public class BSTMap<K extends Comparable<K> , V> implements MapInterface<K, V> { 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; this.left = null; this.right = null; } } private Node root; private int size; // 返回以node为根节点的二分搜索树中，key所在的节点 private Node getNode(Node node, K key) { if(node == null) { return null; } if(key.compareTo(node.key) > 0) { return getNode(node.right, key); }else if(key.compareTo(node.key) < 0) { return getNode(node.left, key); }else { return node; } } @Override public void add(K key, V value) { root = add(root, key, value); } private Node add(Node node, K key, V value) { if(node == null) { size++; return new Node(key, value); } if(key.compareTo(node.key) < 0) { // 加在左子树 node.left = add(node.left, key, value); }else if(key.compareTo(node.key) > 0){ // 加在右子树 node.right = add(node.right, key, value); } // else { // 更新节点 // node.value = value; // } return node; } @Override public V remove(K key) { Node node = getNode(root, key); if(node != null) { root = remove(root, key); return node.value; } return null; } // 查找最小值节点 public Node findMin(Node root) { if(root == null) { return null; } Node cur = root; while (cur.left != null) { cur = cur.left; } return cur; } private Node removeMin(Node node) { if(node.left == null) { Node currentItemRight = node.right; node.right = null; size--; // 返回当前元素的右子树 return currentItemRight; } node.left = removeMin(node.left); return node; } private Node remove(Node node, K key) { if(node == null) { return null; } if(key.compareTo(node.key) > 0) { node.right = remove(node.right, key); return node; }else if(key.compareTo(node.key) < 0) { node.left = remove(node.left, key); return node; }else { // node.e = 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 successor = findMin(node.right); // 改变该后继节点的left指向 successor.left = node.left; // 改变该后继节点的right指向。即删除了该后继节点的子树 successor.right = removeMin(node.right); node.left = node.right = null; return successor; } } @Override public void set(K key, V value) { Node node = getNode(root, key); if(node != null) { node.value = value; }else { // 不存在就添加 add(key, value); } } @Override public V get(K key) { Node node = getNode(root, key); return node != null ? node.value : null; } @Override public int getSize() { return size; } @Override public boolean contains(K key) { Node node = getNode(root, key); return node != null; } @Override public boolean isEmpty() { return size == 0; } // 前序遍历 public void preOrder() { preOrder(root); } private void preOrder(Node node) { if(node == null) { // System.out.println("null"); return ; } System.out.println(node.key + "=>" + node.value); // 遍历该节点的左子树 preOrder(node.left); // 遍历该节点的右子树 preOrder(node.right); } }
复杂度分析
网络异常，图片无法展示
|
二者的关系
其实java底层就是使用map实现的set。
网络异常，图片无法展示
|
LeetCode相关习题
LeetCode 349
- 首先将一个数组元素放在set中，
- 再根据另一个数组中元素判断是否存在
- 存在就删除，防止下一次依旧有相同的加入到返回的数组中。
public int[] intersection(int[] nums1, int[] nums2) { TreeSet<Integer> set = new TreeSet<>(); LinkedList<Integer> arr = new LinkedList<>(); for (int item : nums1) { set.add(item); // 这里的item加入的是不重复的。 } for(int item: nums2) { if(set.contains(item)) { // 返回true，则表示存在 arr.add(item); // 加入后就删除, 防止下一次相同的再次加入。 set.remove(item); } } int[] ints = new int[arr.size()]; for(int i = 0; i < arr.size(); i++) { ints[i] = arr.get(i); } return ints; }
LeetCode 350
TreeMap<Integer, Integer> map = new TreeMap<>(); LinkedList<Integer> arr = new LinkedList<>(); for (int item : nums1) { // map.add(item); // 这里的item加入的是不重复的。 if(map.containsKey(item)) { // 如果存在，就加一 map.put(item, map.get(item) + 1); }else { // 如果没有就直接设置为一 map.put(item, 1); } } for(int item: nums2) { if(map.containsKey(item)) { // 返回true，则表示存在 arr.add(item); map.put(item, map.get(item) - 1); // 存在将value减一 if(map.get(item) == 0) { // 当元素value为0时，删除该元素 map.remove(item); } } } int[] ints = new int[arr.size()]; for(int i = 0; i < arr.size(); i++) { ints[i] = arr.get(i); } return ints;
