集合

不能存放重复元素，分为有序集合 (基于搜索树的实现) 和无序集合 (基于哈希表的实现) 。

集合代码实现

首先，我们先定义一个集合需要用到的接口方法，因为集合的底层实现可以是多样的，只要实现了接口方法的，都可以称为集合。

集合接口定义

public interface Set<E> {
    void add(E e);

    void remove(E e);

    boolean contains(E e);

    int getSize();

    boolean isEmpty();
}

底层为二分搜索树的集合

public class BSTSet<E extends Comparable<E>> implements Set<E> {

    private BST<E> bst;

    public BSTSet() {
        this.bst = new BST<>();
    }

    @Override
    public int getSize() {
        return bst.getSize();
    }

    @Override
    public boolean isEmpty() {
        return bst.isEmpty();
    }

    @Override
    public void add(E e) {
        // bst 本身支持不添加重复的元素
        bst.add(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

}

底层为链表的集合

public class LinkedListSet<E> implements Set<E> {

    private LinkedList<E> linkedList ;

    public LinkedListSet() {
        linkedList = new LinkedList<>();
    }

    @Override
    public void add(E e) {
        // 如果不包含元素，才添加
        if (!contains(e)) {
            linkedList.addFirst(e);
        }
    }

    @Override
    public void remove(E e) {
        linkedList.removeElement(e);
    }

    @Override
    public boolean contains(E e) {
        return linkedList.contains(e);
    }

    @Override
    public int getSize() {
        return linkedList.getSize();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

}

时间复杂度分析

O(logn) 级别的复杂度比 O(n) 级别的要快很多。

LinkedListSet 的时间复杂度分析

void add(E e) ， O(n) 级别

void remove(E e) ， O(n) 级别

boolean contains(E e) ， O(n) 级别

BSTSet 的时间复杂度分析

如上图所示，总共是 h 层，共有如下 T 的节点数：

T = 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(h-1)

根据等比数列的公式可得：

T = (1 * (1 - 2^h )) / (1 - 2) = 2^h -1

结论： h = log(n+1) = O(logn)

那么底层为二分搜索树的集合的复杂度如下：

void add(E e) ， O(logn) 级别

E remove() ， O(logn) 级别

E contains() ， O(logn) 级别

BSTSet 和 LinkedListSet 的性能比较

public class SetMain {

    public static void main(String[] args) {
        String fileName = "F:\\java_projects\\data_structure\\DataStructures\\src\\a-tale-of-two-cities.txt";
        Set<String> bstSet = new BSTSet<>();
        Set<String> linkedListSet = new LinkedListSet<>();
        System.out.println("testSet(bstSet,fileName) = " + testSet(bstSet, fileName));
        System.out.println("testSet(linkedListSet,fileName) = " + testSet(linkedListSet, fileName));
    }

    /**
     * 测试集合的运行时间
     */
    private static double testSet(Set<String> set, String fileName) {
        long startTime = System.nanoTime();
        ArrayList<String> words = new ArrayList<>();
        boolean isSuccesss = FileOperation.readFile("F:\\java_projects\\data_structure\\DataStructures\\src\\a-tale-of-two-cities.txt", words);
        if (isSuccesss) {
            for (String s : words) {
                set.add(s);
            }
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
}

运行结果：

testSet(bstSet,fileName) = 0.418924909

testSet(linkedListSet,fileName) = 7.559209249

总结：BSTSet 的性能比 LinkedListSet 好很多，因为 BSTSet 是 O(logn) 级别的，LinkedListSet 是 O(n) 级别的。

LeetCode 的题目解答

349.两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

解题代码如下：

public int[] intersection(int[] nums1, int[] nums2) {
    TreeSet<Integer> treeSet = new TreeSet<>();
    // 将第一个数组做去重处理
    for (int i : nums1) {
        treeSet.add(i);
    }

    ArrayList<Integer> result = new ArrayList<>();

    for (int i : nums2) {
        if (treeSet.contains(i)) {
            result.add(i);
            // 如果包含了，移除元素
            treeSet.remove(i);
        }
    }
    // 把交集数据放到数组里面并返回
    int[] array = new int[result.size()];
    for (int i = 0; i < result.size(); i++) {
        array[i] = result.get(i);
    }
    return array;
}