专栏首页算法之名数据结构整理 顶

数据结构整理 顶

  • 数组封装

接口

public interface Array<T> {
    T[] getData();
    int getSize();
    int getCapacity();
    boolean isEmpty();
    void addLast(T t);
    void addFirst(T t);
    void add(int index, T t);
    T get(int index);
    T getLast();
    T getFirst();
    void set(int index, T t);
    boolean contains(T t);
    int find(T t);
    void removeElement(T t);
    T remove(int index);
    T removeFirst();
    T removeLast();

    /**
     * 交换两个索引的元素的位置
     * @param i
     * @param j
     */
    void swap(int i,int j);
}

实现类

public class DefaultArray<T> implements Array<T> {
    private static final int factor = 2;
    private T[] data;
    private int size;

    @SuppressWarnings("unchecked")
    public DefaultArray(int capacity) {
        data = (T[]) new Object[capacity];
        size = 0;
    }

    public DefaultArray() {
        this(20);
    }

    @SuppressWarnings("unchecked")
    public DefaultArray(T[] data) {
        this.data = (T[]) new Object[data.length + 1];
        for (int i = 0;i < data.length;i++) {
            this.data[i] = data[i];
        }
        this.size = data.length;
    }

    @Override
    public T[] getData() {
        return data;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public int getCapacity() {
        return data.length;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void addLast(T value) {
        add(size,value);
    }

    @Override
    public void addFirst(T value) {
        add(0,value);
    }

    @Override
    public void add(int index,T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加失败,要求index >=0且index<=size");
        }
        for (int i = size;i > index;i--) {
            data[i] = data[i - 1];
        }
        data[index] = value;
        size++;
        if (size == data.length) {
            resize(getCapacity() * factor);
        }
    }

    @Override
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("获取失败,index参数错误");
        }
        return data[index];
    }

    @Override
    public T getLast() {
        return get(size - 1);
    }

    @Override
    public T getFirst() {
        return get(0);
    }

    @Override
    public void set(int index,T value) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("设置失败,index参数错误");
        }
        data[index] = value;
    }

    @Override
    public boolean contains(T value) {
        for (int i = 0;i < size;i++) {
            if (data[i].equals(value)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int find(T value) {
        for (int i = 0;i < size;i++) {
            if (data[i].equals(value)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public void removeElement(T value) {
        int index = find(value);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("移除失败,index参数错误");
        }
        T ret = data[index];
        for (int i = index;i < size;i++) {
            data[i] = data[i + 1];
        }
        size--;
        if (size <= getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / factor);
        }
        return ret;
    }

    @Override
    public T removeFirst() {
        return remove(0);
    }

    @Override
    public T removeLast() {
        return remove(size - 1);
    }

    @Override
    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("索引非法");
        }
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    @SuppressWarnings("unchecked")
    private void resize(int capacity) {
        if (capacity == size) {
            capacity++;
        }
        T[] newData = (T[]) new Object[capacity];
        for (int i = 0;i < size;i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("DefaultArray(data=[");
        for (int i = 0;i < size - 1;i++) {
            builder.append(data[i] + ",");
        }
        builder.append(data[size -1] + "], size=" + size);
        return builder.toString();
    }
}

调用

public class ArrayMain {
    public static void main(String[] args) {
        Array<Integer> array = new DefaultArray<>(3);
        array.addLast(66);
        array.addLast(99);
        array.addLast(88);
        System.out.println(array);
        array.add(1,77);
        array.addFirst(100);
        array.set(4,11);
        array.remove(2);
        System.out.println(array);
        System.out.println(array.get(3));
        array.remove(1);
        array.removeFirst();
        array.removeFirst();
        System.out.println(array);
    }
}

运行结果

DefaultArray(data=[66,99,88], size=3 DefaultArray(data=[100,66,99,11], size=4 11 DefaultArray(data=[11], size=1

  • 时间复杂度的简单示例

O(n) 线性关系计算

计算整形数组的和

@FunctionalInterface
public interface On {
    int compute(Integer[] nums);
}
public class SumOn {
    public int sum(Array<Integer> array,On on) {
        return on.compute(array.getData());
    }
}
public class Main {
    public static void main(String[] args) {
        Array<Integer> array = new DefaultArray<>(new Integer[]{1,2,3,4,5,6,7});
        SumOn sumOn = new SumOn();
        int sum = sumOn.sum(array, nums ->
                Stream.of(nums).reduce((x, y) -> x + y).get());
        System.out.println(sum);
    }
}

运行结果

28

线性方程: T = c1*n + c2,而O(n)指的是忽略常数c1,c2。如以下关系,无论计算中有具体多少步执行

T = 2*n + 2 O(n)

T = 2000*n + 10000 O(n) 渐进时间复杂度

T = 1*n*n +0 O(n^2) 虽然这里的常数很小,描述n趋近于无穷的情况

T = 2*n*n + 300*n + 10 O(n^2) 低阶项300*n会被忽略

对于Array各操作的时间复杂度

添加操作

addLast(value) O(1)

addFirst(value) O(n)

add(index,value) 严格计算需要概率论,平均来说 O(n/2) = O(n)

从整体上看,添加操作是一个O(n)级别的时间复杂度

扩容

resize O(n)

删除操作

removeLast() O(1)

removeFirst() O(n)

remove(index) O(n/2) = O(n)

从整体上看,删除操作是一个O(n)级别的时间复杂度

缩容

resize O(n)

修改操作

set(index,value) O(1)

swap(i,j) O(1)

查找操作

get(index) O(1)

contains(value) O(n)

find(value) O(n)

  • 数组栈封装

栈是数组的子集,是一种后进先出的数据结构

接口

public interface Stack<T> {
    /**
     * 入栈
     * @param t
     */
    void push(T t);

    /**
     * 出栈
     * @return
     */
    T pop();

    /**
     * 获取栈顶元素
     * @return
     */
    T peek();
    int getSize();
    boolean isEmpty();
}

实现类

@ToString
public class ArrayStack<T> implements Stack<T> {
    private Array<T> array;

    public ArrayStack(int capacity) {
        array = new DefaultArray<>(capacity);
    }

    public ArrayStack() {
        array = new DefaultArray<>();
    }

    @Override
    public void push(T value) {
        array.addLast(value);
    }

    @Override
    public T pop() {
        return array.removeLast();
    }

    @Override
    public T peek() {
        return array.getLast();
    }

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

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

    public int getCapacity() {
        return array.getCapacity();
    }
}

调用

public class StackMain {
    public static void main(String[] args) {
        Stack<Integer> stack = new ArrayStack<>(5);
        for (int i = 0;i < 5;i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
}

运行结果

ArrayStack(array=DefaultArray(data=[0], size=1) ArrayStack(array=DefaultArray(data=[0,1], size=2) ArrayStack(array=DefaultArray(data=[0,1,2], size=3) ArrayStack(array=DefaultArray(data=[0,1,2,3], size=4) ArrayStack(array=DefaultArray(data=[0,1,2,3,4], size=5) ArrayStack(array=DefaultArray(data=[0,1,2,3], size=4)

对于Stack各操作的时间复杂度

  • push(value) O(1) 均摊
  • Pop() O(1) 均摊
  • peek() O(1)
  • getSize() O(1)
  • isEmpty() O(1)

LeetCode算法题 https://leetcode-cn.com/problems/valid-parentheses/

这是LeetCode的第20题——有效的括号

我们先用JDK的栈来完成,这里的Stack为java.util.Stack,该类继承于Vector

public class JavaSolution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0;i < s.length();i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }else {
                if (stack.isEmpty()) {
                    return false;
                }
                char topChar = stack.pop();
                if (c == ')' && topChar != '(') {
                    return false;
                }
                if (c == ']' && topChar != '[') {
                    return false;
                }
                if (c == '}' && topChar != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        JavaSolution solution = new JavaSolution();
        String patten = "{}[()]";
        System.out.println(solution.isValid(patten));
    }
}

运行结果

true

提交给LeetCode

当然我们也可以使用我们自己封装的栈对象来处理

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new ArrayStack<>();
        for (int i = 0;i < s.length();i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }else {
                if (stack.isEmpty()) {
                    return false;
                }
                char topChar = stack.pop();
                if (c == ')' && topChar != '(') {
                    return false;
                }
                if (c == ']' && topChar != '[') {
                    return false;
                }
                if (c == '}' && topChar != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String patten = "{[()]}";
        boolean valid = solution.isValid(patten);
        System.out.println(valid);
    }
}

运行结果

true

  • 数组队列封装

队列的操作是数组的子集,只能从一端添加元素(队尾),从另一端取出元素(队首),是一种先进先出的数据结构

接口

public interface Queue<T> {
    /**
     * 入队
     * @param t
     */
    void enqueue(T t);

    /**
     * 出队
     * @return
     */
    T dequeue();

    /**
     * 获取队首元素
     * @return
     */
    T getFront();
    int getSize();
    boolean isEmpty();
}

实现类

@ToString
public class ArrayQueue<T> implements Queue<T> {
    private Array<T> array;

    public ArrayQueue(int capacity) {
        array = new DefaultArray<>(capacity);
    }

    public ArrayQueue() {
        array = new DefaultArray<>();
    }

    @Override
    public void enqueue(T value) {
        array.addLast(value);
    }

    @Override
    public T dequeue() {
        return array.removeFirst();
    }

    @Override
    public T getFront() {
        return array.getFirst();
    }

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

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

    public int getCapaticy() {
        return array.getCapacity();
    }
}

调用

public class QueueMain {
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayQueue<>(10);
        for (int i = 0;i < 10;i++) {
            queue.enqueue(i);
            System.out.println(queue);

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

运行结果

ArrayQueue(array=DefaultArray(data=[0], size=1) ArrayQueue(array=DefaultArray(data=[0,1], size=2) ArrayQueue(array=DefaultArray(data=[0,1,2], size=3) ArrayQueue(array=DefaultArray(data=[1,2], size=2) ArrayQueue(array=DefaultArray(data=[1,2,3], size=3) ArrayQueue(array=DefaultArray(data=[1,2,3,4], size=4) ArrayQueue(array=DefaultArray(data=[1,2,3,4,5], size=5) ArrayQueue(array=DefaultArray(data=[2,3,4,5], size=4) ArrayQueue(array=DefaultArray(data=[2,3,4,5,6], size=5) ArrayQueue(array=DefaultArray(data=[2,3,4,5,6,7], size=6) ArrayQueue(array=DefaultArray(data=[2,3,4,5,6,7,8], size=7) ArrayQueue(array=DefaultArray(data=[3,4,5,6,7,8], size=6) ArrayQueue(array=DefaultArray(data=[3,4,5,6,7,8,9], size=7) ArrayQueue(array=DefaultArray(data=[3,4,5,6,7,8,9,10], size=8)

对于ArrayQueue操作的时间复杂度

enqueue(value) O(1) 均摊

dequeue() O(n)

getFront() O(1)

getSize() O(1)

isEmpty() O(1)

鉴于数组队列每一次出队都会将队列中的所有元素前移,时间复杂度为O(n),所以为了克制这种情况,我们需要构建一个循环队列,把数组看成首尾相接的一个环,出队时无需移动队列中的元素。此时将不再复用Array的实现。

  • 循环队列封装

实现类

public class LoopQueue<T> implements Queue<T> {
    private T[] data;
    /**
     * 循环队列队首
     */
    private int front;
    /**
     * 循环队列队尾
     */
    private int tail;
    /**
     * 循环队列成员数量
     */
    private int size;
    /**
     * 扩容因子
     */
    private static final int factor = 2;

    @SuppressWarnings("unchecked")
    public LoopQueue(int capacity) {
        data = (T[]) new Object[capacity + 1];
        front = tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(20);
    }

    public int getCapacity() {
        return data.length - 1;
    }

    @Override
    public void enqueue(T value) {
        //判断队列是否已满
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * factor);
        }
        data[tail] = value;
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("无法从空队列出队");
        }
        T ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if (size <= getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / factor);
        }
        return ret;
    }

    @Override
    public T getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @SuppressWarnings("unchecked")
    private void resize(int capacity) {
        T[] newData = (T[]) new Object[capacity + 1];
        for (int i = 0;i < size;i++) {
            //将老数组的元素放入新数组时,将重新将0定位新数组的front
            newData[i] = data[(front + i) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("LoopQueue{data=[");
        for (int i = 0;i < size - 1;i++) {
            builder.append(data[(front + i) % data.length] + ",");
        }
        builder.append(data[(tail - 1) % data.length] + "], size=" + size);
        return builder.toString();
    }
}

调用

public class QueueMain {
    public static void main(String[] args) {
        Queue<Integer> queue = new LoopQueue<>(7);
        for (int i = 0;i <= 10;i++) {
            queue.enqueue(i);
            System.out.println(queue);

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

运行结果

LoopQueue{data=[0], size=1 LoopQueue{data=[0,1], size=2 LoopQueue{data=[0,1,2], size=3 LoopQueue{data=[1,2], size=2 LoopQueue{data=[1,2,3], size=3 LoopQueue{data=[1,2,3,4], size=4 LoopQueue{data=[1,2,3,4,5], size=5 LoopQueue{data=[2,3,4,5], size=4 LoopQueue{data=[2,3,4,5,6], size=5 LoopQueue{data=[2,3,4,5,6,7], size=6 LoopQueue{data=[2,3,4,5,6,7,8], size=7 LoopQueue{data=[3,4,5,6,7,8], size=6 LoopQueue{data=[3,4,5,6,7,8,9], size=7 LoopQueue{data=[3,4,5,6,7,8,9,10], size=8

对于LoopQueue操作的时间复杂度

enqueue(value) O(1) 均摊

dequeue() O(1) 均摊

getFront() O(1)

getSize() O(1)

isEmpty() O(1)

两种队列的性能测试

public class TestQueueMain {
    private static double testQueue(Queue<Integer> q,int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0;i < opCount;i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0;i < opCount;i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 100000;
        Queue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue,opCount);
        System.out.println("ArrayQueue,time: " + time1 + " s");

        Queue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue,opCount);
        System.out.println("LoopQueue,time: " + time2 + " s");
    }
}

测试结果

ArrayQueue,time: 2.737708686 s LoopQueue,time: 0.011393786 s

  • 单向链表封装

之前的动态数组,栈,队列都是底层依托静态数组,靠resize()解决固定容量问题,而链表是真正的动态数据结构,不需要处理固定容量的问题。但缺点也很明显,丧失了随机访问的能力。不适合用于索引有语义的情况。

接口

public interface List<T> {
    int getSize();
    boolean isEmpty();
    void addFirst(T t);
    void add(int index,T t);
    void addLast(T t);
    T get(int index);
    T getFirst();
    T getLast();
    void set(int index,T t);
    boolean contains(T t);
    T remove(int index);
    T removeFirst();
    T removeLast();
    void removeElement(T t);
}

实现类

public class LinkedList<T> implements List<T> {
    @AllArgsConstructor
    @Data
    private class Node {
        private T element;
        private Node next;

        public Node(T element) {
            this(element,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }

    /**
     * 链表虚拟头节点
     */
    private Node dummyHead;
    private int size;

    public LinkedList() {
        dummyHead = new Node();
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(int index,T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加错误,非法索引");
        }

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.getNext();
        }
        prev.setNext(new Node(value, prev.getNext()));
        size++;

    }

    @Override
    public void addFirst(T value) {
        add(0,value);
    }

    @Override
    public void addLast(T value) {
        add(size,value);
    }

    @Override
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("获取错误,非法索引");
        }
        Node cur = dummyHead.getNext();
        for (int i = 0;i < index;i++) {
            cur = cur.getNext();
        }
        return cur.getElement();
    }

    @Override
    public T getFirst() {
        return get(0);
    }

    @Override
    public T getLast() {
        return get(size - 1);
    }

    @Override
    public void set(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("设置错误,非法索引");
        }
        Node cur = dummyHead.getNext();
        for (int i = 0;i < index;i++) {
            cur = cur.getNext();
        }
        cur.setElement(value);
    }

    @Override
    public boolean contains(T value) {
        Node cur = dummyHead.getNext();
        while (cur != null) {
            if (cur.getElement().equals(value)) {
                return true;
            }
            cur = cur.getNext();
        }
        return false;
    }

    @Override
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("删除错误,非法索引");
        }
        Node prev = dummyHead;
        for (int i = 0;i < index;i++) {
            prev = prev.getNext();
        }
        Node retNode = prev.getNext();
        prev.setNext(retNode.getNext());
        retNode.setNext(null);
        size--;
        return retNode.getElement();
    }

    @Override
    public T removeFirst() {
        return remove(0);
    }

    @Override
    public T removeLast() {
        return remove(size - 1);
    }

    @Override
    public void removeElement(T value) {
        Node pre = dummyHead;
        while (pre.getNext() != null) {
            if (value.equals(pre.getNext().getElement())) {
                Node delNode = pre.getNext();
                pre.setNext(delNode.getNext());
                delNode.setNext(null);
                size--;
                break;
            }
            pre = pre.getNext();
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node cur = dummyHead.getNext();
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.getNext();
        }
        builder.append("NULL");
        return builder.toString();
    }
}

调用

public class ListMain {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0;i < 5;i++) {
            linkedList.add(i,i);
            System.out.println(linkedList);
        }
        linkedList.add(3,666);
        System.out.println(linkedList);

        linkedList.addLast(777);
        System.out.println(linkedList);

        linkedList.set(4,888);
        System.out.println(linkedList);

        System.out.println(linkedList.get(5));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        System.out.println(linkedList.contains(3));

        linkedList.removeLast();
        System.out.println(linkedList);

        linkedList.remove(4);
        System.out.println(linkedList);

        linkedList.removeFirst();
        System.out.println(linkedList);

        linkedList.removeLast();
        System.out.println(linkedList);
        linkedList.removeElement(2);
        System.out.println(linkedList);
        System.out.println(linkedList.getLast());
    }
}

运行结果

0->NULL 0->1->NULL 0->1->2->NULL 0->1->2->3->NULL 0->1->2->3->4->NULL 0->1->2->666->3->4->NULL 0->1->2->666->3->4->777->NULL 0->1->2->666->888->4->777->NULL 4 0 777 false 0->1->2->666->888->4->NULL 0->1->2->666->4->NULL 1->2->666->4->NULL 1->2->666->NULL 1->666->NULL 666

LinkedList各操作的时间复杂度

添加操作 O(n)

addLast(value) O(n)

addFirst(value) O(1)

add(index,value) O(n/2) = O(n)

删除操作 O(n)

removeLast() O(n)

removeFirst() O(1)

remove(index) O(n/2) = O(n)

removeElement(value) O(n)

修改操作

set(index,value) O(n)

查找操作 O(n)

get(index) O(n)

contains(value) O(n)

由于链表中对链表头的各操作都是O(1)的,对应于栈这种数据结构,是非常方便的,而且也无需扩容这一概念。

  • 链表栈封装

实现类

@ToString
public class LinkedListStack<T> implements Stack<T> {
    private List<T> list;

    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public void push(T value) {
        list.addFirst(value);
    }

    @Override
    public T pop() {
        return list.removeFirst();
    }

    @Override
    public T peek() {
        return list.getFirst();
    }

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

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

调用

public class StackMain {
    public static void main(String[] args) {
        Stack<Integer> stack = new LinkedListStack<>();
        for (int i = 0;i < 5;i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
}

运行结果

LinkedListStack(list=0->NULL) LinkedListStack(list=1->0->NULL) LinkedListStack(list=2->1->0->NULL) LinkedListStack(list=3->2->1->0->NULL) LinkedListStack(list=4->3->2->1->0->NULL) LinkedListStack(list=3->2->1->0->NULL)

两种栈的性能测试

public class TestStackMain {
    private static double testStack(Stack<Integer> stack,int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0;i < opCount;i++) {
            stack.push(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0;i < opCount;i++) {
            stack.pop();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 10000000;
        Stack<Integer> arrayStack = new ArrayStack<>();
        double time1 = testStack(arrayStack,opCount);
        System.out.println("ArrayStack,time: " + time1 + " s");

        Stack<Integer> linkedListStack = new LinkedListStack<>();
        double time2 = testStack(linkedListStack,opCount);
        System.out.println("LinkedListStack,time: " + time2 + " s");
    }
}

测试结果

ArrayStack,time: 0.891863504 s LinkedListStack,time: 3.731664658 s

对于这个测试结果来说,LinkedListStack要明显高于ArrayStack,这主要是Java的分配内存的特性决定,因为LinkedListStack有更多的new操作,要不断的分配内存空间给新的对象node。但这里要说明的是,其实它们两个在算法层面的时间复杂度是一致的。

  • 链表队列封装

由于队列的特性,一端进,一端出,所以我们要添加一个尾节点,所以LinkedList无法复用。

实现类

public class LinkedListQueue<T> implements Queue<T> {
    @AllArgsConstructor
    @Data
    private class Node {
        private T element;
        private Node next;

        public Node(T element) {
            this(element,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }

    /**
     * 队列头节点
     */
    private Node head;
    /**
     * 队列尾节点
     */
    private Node tail;
    /**
     * 队列元素个数
     */
    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public void enqueue(T value) {
        //当整个队列为空的时候
        if (tail == null) {
            tail = new Node(value);
            head = tail;
        }else { //从尾部入队
            tail.setNext(new Node(value));
            tail = tail.getNext();
        }
        size++;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("无法从空队列出队");
        }
        //从头部出队
        Node retNode = head;
        head = head.getNext();
        retNode.setNext(null);
        if (head == null) {
            tail = null;
        }
        size--;
        return retNode.getElement();
    }

    @Override
    public T getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        return head.getElement();
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Queue: front ");
        Node cur = head;
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.getNext();
        }
        builder.append("NULL tail");
        return builder.toString();
    }
}

调用

public class QueueMain {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedListQueue<>();
        for (int i = 0;i <= 10;i++) {
            queue.enqueue(i);
            System.out.println(queue);

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

运行结果

Queue: front 0->NULL tail Queue: front 0->1->NULL tail Queue: front 0->1->2->NULL tail Queue: front 1->2->NULL tail Queue: front 1->2->3->NULL tail Queue: front 1->2->3->4->NULL tail Queue: front 1->2->3->4->5->NULL tail Queue: front 2->3->4->5->NULL tail Queue: front 2->3->4->5->6->NULL tail Queue: front 2->3->4->5->6->7->NULL tail Queue: front 2->3->4->5->6->7->8->NULL tail Queue: front 3->4->5->6->7->8->NULL tail Queue: front 3->4->5->6->7->8->9->NULL tail Queue: front 3->4->5->6->7->8->9->10->NULL tail

对三种队列进行性能测试

public class TestQueueMain {
    private static double testQueue(Queue<Integer> q,int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0;i < opCount;i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0;i < opCount;i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 100000;
        Queue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue,opCount);
        System.out.println("ArrayQueue,time: " + time1 + " s");

        Queue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue,opCount);
        System.out.println("LoopQueue,time: " + time2 + " s");

        Queue<Integer> linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue,opCount);
        System.out.println("LinkedListQueue,time: " + time3 + " s");
    }
}

测试结果

ArrayQueue,time: 2.727521755 s LoopQueue,time: 0.011994964 s LinkedListQueue,time: 0.008463007 s

但是如果我们将opCount设为1千万,arrayQueue不参与,因为arrayQueue是O(n)级别的,时间过长,无法完成运算

public class TestQueueMain {
    private static double testQueue(Queue<Integer> q,int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0;i < opCount;i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0;i < opCount;i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 10000000;
//        Queue<Integer> arrayQueue = new ArrayQueue<>();
//        double time1 = testQueue(arrayQueue,opCount);
//        System.out.println("ArrayQueue,time: " + time1 + " s");

        Queue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue,opCount);
        System.out.println("LoopQueue,time: " + time2 + " s");

        Queue<Integer> linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue,opCount);
        System.out.println("LinkedListQueue,time: " + time3 + " s");
    }
}

测试结果

LoopQueue,time: 1.198824936 s LinkedListQueue,time: 3.531655449 s

则此处LinkedListQueue比LoopQueue高的原因在之前的栈测试中已经说过了。通过查看GC日志-XX:+PrintGCDetails,我们可以看到

[GC (Allocation Failure) [PSYoungGen: 65536K->10720K(76288K)] 65536K->47444K(251392K), 0.0399149 secs] [Times: user=0.47 sys=0.03, real=0.04 secs] [GC (Allocation Failure) [PSYoungGen: 76256K->10736K(141824K)] 112980K->102884K(316928K), 0.0615931 secs] [Times: user=0.74 sys=0.03, real=0.06 secs] [GC (Allocation Failure) [PSYoungGen: 128805K->10720K(141824K)] 220954K->185957K(317440K), 0.1094546 secs] [Times: user=1.09 sys=0.07, real=0.11 secs] [Full GC (Ergonomics) [PSYoungGen: 10720K->0K(141824K)] [ParOldGen: 175237K->83146K(279552K)] 185957K->83146K(421376K), [Metaspace: 3396K->3396K(1056768K)], 0.6877482 secs] [Times: user=4.42 sys=0.04, real=0.68 secs] LoopQueue,time: 1.213829799 s [GC (Allocation Failure) [PSYoungGen: 131072K->10752K(196608K)] 214218K->168218K(476160K), 0.4136930 secs] [Times: user=5.33 sys=0.01, real=0.42 secs] [GC (Allocation Failure) [PSYoungGen: 196608K->10752K(272896K)] 354074K->354714K(616960K), 0.9071643 secs] [Times: user=11.66 sys=0.08, real=0.91 secs] [Full GC (Ergonomics) [PSYoungGen: 10752K->0K(272896K)] [ParOldGen: 343962K->271533K(605696K)] 354714K->271533K(878592K), [Metaspace: 3479K->3479K(1056768K)], 1.8924275 secs] [Times: user=24.48 sys=0.03, real=1.89 secs] LinkedListQueue,time: 3.412228277 s Heap PSYoungGen total 272896K, used 131467K [0x000000076ab00000, 0x0000000792600000, 0x00000007c0000000) eden space 262144K, 50% used [0x000000076ab00000,0x0000000772b62e80,0x000000077ab00000) from space 10752K, 0% used [0x000000077ab00000,0x000000077ab00000,0x000000077b580000) to space 185344K, 0% used [0x0000000787100000,0x0000000787100000,0x0000000792600000) ParOldGen total 605696K, used 271533K [0x00000006c0000000, 0x00000006e4f80000, 0x000000076ab00000) object space 605696K, 44% used [0x00000006c0000000,0x00000006d092b670,0x00000006e4f80000) Metaspace used 3486K, capacity 4566K, committed 4864K, reserved 1056768K class space used 376K, capacity 390K, committed 512K, reserved 1048576K

通过GC日志,我们可以看到有大量的对象进入了老年代,并没有在年轻代被回收,以至于发生了全GC。我们调整JVM内存来看一下-Xmx1G -Xms1G

[GC (Allocation Failure) [PSYoungGen: 260301K->43511K(305664K)] 260301K->83257K(1005056K), 0.0813630 secs] [Times: user=0.99 sys=0.04, real=0.08 secs] LoopQueue,time: 0.443129398 s [GC (Allocation Failure) [PSYoungGen: 305655K->43495K(305664K)] 345401K->254481K(1005056K), 1.0359483 secs] [Times: user=12.20 sys=0.14, real=1.04 secs] LinkedListQueue,time: 1.261171544 s Heap PSYoungGen total 305664K, used 223003K [0x00000007aab00000, 0x00000007c0000000, 0x00000007c0000000) eden space 262144K, 68% used [0x00000007aab00000,0x00000007b5a4d0e8,0x00000007bab00000) from space 43520K, 99% used [0x00000007bd580000,0x00000007bfff9dc8,0x00000007c0000000) to space 43520K, 0% used [0x00000007bab00000,0x00000007bab00000,0x00000007bd580000) ParOldGen total 699392K, used 210985K [0x0000000780000000, 0x00000007aab00000, 0x00000007aab00000) object space 699392K, 30% used [0x0000000780000000,0x000000078ce0a708,0x00000007aab00000) Metaspace used 3488K, capacity 4566K, committed 4864K, reserved 1056768K class space used 376K, capacity 390K, committed 512K, reserved 1048576K

通过调整JVM内存,我们可以看到全GC消失了,所使用的时间大幅度减少。但是我们可以看到eden区的使用空间过小,只有68%,所以我们要调整新生代的内存分配比例

-XX:+PrintGCDetails -Xmx1G -Xms1G -XX:+UseParallelGC -XX:+UseCompressedOops -XX:SurvivorRatio=4 -XX:ParallelGCThreads=8

[GC (Allocation Failure) [PSYoungGen: 233472K->57831K(291328K)] 233472K->174728K(990720K), 0.1696696 secs] [Times: user=1.25 sys=0.09, real=0.17 secs] LoopQueue,time: 0.521021115 s [GC (Allocation Failure) [PSYoungGen: 291303K->57831K(291328K)] 408200K->279688K(990720K), 0.6708571 secs] [Times: user=5.25 sys=0.10, real=0.67 secs] LinkedListQueue,time: 0.866029237 s Heap PSYoungGen total 291328K, used 290384K [0x00000007aab00000, 0x00000007c0000000, 0x00000007c0000000) eden space 233472K, 99% used [0x00000007aab00000,0x00000007b8e1a330,0x00000007b8f00000) from space 57856K, 99% used [0x00000007bc780000,0x00000007bfff9dc8,0x00000007c0000000) to space 57856K, 0% used [0x00000007b8f00000,0x00000007b8f00000,0x00000007bc780000) ParOldGen total 699392K, used 221857K [0x0000000780000000, 0x00000007aab00000, 0x00000007aab00000) object space 699392K, 31% used [0x0000000780000000,0x000000078d8a84f8,0x00000007aab00000) Metaspace used 3488K, capacity 4566K, committed 4864K, reserved 1056768K class space used 376K, capacity 390K, committed 512K, reserved 1048576K

通过调整eden区和survivor区(包括from和to)的比例,我们可以看到eden区的使用效率提升到了99%,而LinkedListQueue的运行时间也由1.261171544 s降到了0.866029237 s。

LeetCode算法题https://leetcode-cn.com/problems/remove-linked-list-elements/submissions/

这是LeetCode的第203题,移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

我们先定义一个ListNode

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
    }
}
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //移除所有可能值为val的头部节点
        while (head != null && head.val == val) {
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }
        if (head == null) {
            return null;
        }
        //移除所有可能值为val的中间节点
        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                prev = prev.next;
            }
        }
        return head;
    }
}

提交后,结果如下

当然除了特殊处理头节点以外,我们还可以建立虚拟头节点

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //建立虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        //移除所有可能值为val的中间节点
        ListNode prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }
}

提交给LeetCode

自己实现一个测试用例

改写ListNode

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
    }

    /**
     * 通过一个数组转化成一个链表
     * @param arr
     */
    public ListNode(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }
        this.val = arr[0];
        ListNode cur = this;
        for (int i = 1;i < arr.length;i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            builder.append(cur.val + "->");
            cur = cur.next;
        }
        builder.append("NULL");
        return builder.toString();
    }
}
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //建立虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        //移除所有可能值为val的中间节点
        ListNode prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        int[] values = {1,2,6,3,4,5,6};
        ListNode node = new ListNode(values);
        System.out.println(node);
        Solution solution = new Solution();
        ListNode listNode = solution.removeElements(node, 6);
        System.out.println(listNode);
    }
}

测试结果

1->2->6->3->4->5->6->NULL 1->2->3->4->5->NULL

  • 递归

我们先来看一个求和的递归

public class Sum {
    private static int sum(int[] arr) {
        return sum(arr,0);
    }

    private static int sum(int[] arr,int l) {
        //求解最基本的问题
        if (l == arr.length) {
            return 0;
        }
        //把原问题转化成更小的问题
        return arr[l] + sum(arr,l + 1);
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
        System.out.println(sum(arr));
    }
}

运行结果

45

  • 链表的递归性

链表具有天然的递归性,它可以表示为头节点+少了头节点的链表。

使用递归来求解LeetCode的第203题

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //求解最基本的问题
        if (head == null) {
            return null;
        }
        //把原问题转化成更小的问题
        //此时把链表拆分成头节点+一个不包含头节点的链表
        ListNode node = removeElements(head.next, val);
        //拼接头节点
        if (head.val == val) {
            return node;
        }else {
            head.next = node;
            return head;
        }
    }

    public static void main(String[] args) {
        int[] values = {1,2,6,3,4,5,6};
        ListNode node = new ListNode(values);
        System.out.println(node);
        Solution solution = new Solution();
        ListNode listNode = solution.removeElements(node, 6);
        System.out.println(listNode);
    }
}

运行结果

1->2->6->3->4->5->6->NULL 1->2->3->4->5->NULL

在LeetCode上提交

最后改写成一个简洁的表述

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //求解最基本的问题
        if (head == null) {
            return null;
        }
        //把原问题转化成更小的问题
        //此时把链表拆分成头节点+一个不包含头节点的链表
        head.next = removeElements(head.next, val);
        //是否拼接头节点
        return head.val == val?head.next : head;
    }

    public static void main(String[] args) {
        int[] values = {1,2,6,3,4,5,6};
        ListNode node = new ListNode(values);
        System.out.println(node);
        Solution solution = new Solution();
        ListNode listNode = solution.removeElements(node, 6);
        System.out.println(listNode);
    }
}

运行结果

1->2->6->3->4->5->6->NULL 1->2->3->4->5->NULL

调试链表的递归性

public class Solution {
    public ListNode removeElements(ListNode head, int val,int depth) {
        String depthString = generateDepthString(depth);
        System.out.print(depthString);
        System.out.println("调用: 删除 " + val + "在 " + head + "中");
        //求解最基本的问题
        if (head == null) {
            System.out.print(depthString);
            System.out.println("返回:" + head);
            return null;
        }
        //把原问题转化成更小的问题
        //此时把链表拆分成头节点+一个不包含头节点的链表
        ListNode node = removeElements(head.next, val,depth + 1);
        System.out.print(depthString);
        System.out.println("删除 " + val + "之后: " + node);
        //是否拼接头节点
        ListNode ret;
        if (head.val == val) {
            ret = node;
        }else {
            head.next = node;
            ret = head;
        }
        System.out.print(depthString);
        System.out.println("返回: " + ret);
        return ret;
    }

    private String generateDepthString(int depth) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i < depth;i++) {
            builder.append("--");
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        int[] values = {1,2,6,3,4,5,6};
        ListNode node = new ListNode(values);
        System.out.println(node);
        Solution solution = new Solution();
        ListNode listNode = solution.removeElements(node, 6,0);
        System.out.println(listNode);
    }
}

运行结果

1->2->6->3->4->5->6->NULL 调用: 删除 6在 1->2->6->3->4->5->6->NULL中 --调用: 删除 6在 2->6->3->4->5->6->NULL中 ----调用: 删除 6在 6->3->4->5->6->NULL中 ------调用: 删除 6在 3->4->5->6->NULL中 --------调用: 删除 6在 4->5->6->NULL中 ----------调用: 删除 6在 5->6->NULL中 ------------调用: 删除 6在 6->NULL中 --------------调用: 删除 6在 null中 --------------返回:null ------------删除 6之后: null ------------返回: null ----------删除 6之后: null ----------返回: 5->NULL --------删除 6之后: 5->NULL --------返回: 4->5->NULL ------删除 6之后: 4->5->NULL ------返回: 3->4->5->NULL ----删除 6之后: 3->4->5->NULL ----返回: 3->4->5->NULL --删除 6之后: 3->4->5->NULL --返回: 2->3->4->5->NULL 删除 6之后: 2->3->4->5->NULL 返回: 1->2->3->4->5->NULL 1->2->3->4->5->NULL

  • 单向链表的递归改写

实现类

public class RecursiveLinkedList<T> implements List<T> {
    @AllArgsConstructor
    @Data
    private class Node {
        private T element;
        private Node next;

        public Node(T element) {
            this(element,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }

    /**
     * 链表虚拟头节点
     */
    private Node dummyHead;
    private int size;

    public RecursiveLinkedList() {
        dummyHead = new Node();
        size = 0;
    }
    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void addFirst(T value) {
        add(0,value);
    }

    @Override
    public void add(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加错误,非法索引");
        }
        dummyHead = add(-1,index,dummyHead,value);
    }

    private Node add(int i,int index,Node node,T value) {
        if (i == index - 1) {
            size++;
            node.setNext(new Node(value,node.getNext()));
            return node;
        }
        node.setNext(add(i + 1,index,node.getNext(),value));
        return node;
    }

    @Override
    public void addLast(T value) {
        add(size,value);
    }

    @Override
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("查找错误,非法索引");
        }
        return get(0,index,dummyHead.getNext());
    }

    private T get(int i,int index,Node node) {
        if (i == index) {
            return node.getElement();
        }
        return get(i + 1,index,node.getNext());
    }

    @Override
    public T getFirst() {
        return get(0);
    }

    @Override
    public T getLast() {
        return get(size - 1);
    }

    @Override
    public void set(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("更新错误,非法索引");
        }
        set(0,index,dummyHead.getNext(),value);
    }

    private void set(int i,int index,Node node,T value) {
        if (i == index) {
            node.setElement(value);
            return;
        }
        set(i + 1,index,node.getNext(),value);
    }

    @Override
    public boolean contains(T value) {
        return contains(dummyHead.getNext(),value);
    }

    private boolean contains(Node node,T value) {
        if (node == null) {
            return false;
        }
        if (node.getElement().equals(value)) {
            return true;
        }
        return contains(node.getNext(),value);

    }

    @Override
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("删除错误,非法索引");
        }
        return remove(-1,index,dummyHead).getElement();
    }

    private Node remove(int i,int index,Node node) {
        if (i == index - 1) {
            Node ret = node.getNext();
            node.setNext(ret.getNext());
            ret.setNext(null);
            size--;
            return ret;
        }
        return remove(i + 1,index,node.getNext());
    }

    @Override
    public T removeFirst() {
        return remove(0);
    }

    @Override
    public T removeLast() {
        return remove(size - 1);
    }

    @Override
    public void removeElement(T value) {
        dummyHead = removeElement(dummyHead,value);
    }

    private Node removeElement(Node node,T value) {
        if (node.getNext() == null) {
            return null;
        }
        else {
            if (value.equals(node.getNext().getElement())) {
                Node delNode = node.getNext();
                node.setNext(delNode.getNext());
                delNode.setNext(null);
                size--;
                return node;
            }
        }
        node.setNext(removeElement(node.getNext(),value));
        return node;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node cur = dummyHead.getNext();
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.getNext();
        }
        builder.append("NULL");
        return builder.toString();
    }
}

调用

public class ListMain {
    public static void main(String[] args) {
        List<Integer> linkedList = new RecursiveLinkedList<>();
        for (int i = 0;i < 5;i++) {
            linkedList.add(i,i);
            System.out.println(linkedList);
        }
        linkedList.add(3,666);
        System.out.println(linkedList);

        linkedList.addLast(777);
        System.out.println(linkedList);

        linkedList.set(4,888);
        System.out.println(linkedList);

        System.out.println(linkedList.get(5));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        System.out.println(linkedList.contains(3));

        linkedList.removeLast();
        System.out.println(linkedList);

        linkedList.remove(4);
        System.out.println(linkedList);

        linkedList.removeFirst();
        System.out.println(linkedList);

        linkedList.removeLast();
        System.out.println(linkedList);
        linkedList.removeElement(2);
        System.out.println(linkedList);
        System.out.println(linkedList.getLast());
    }
}

运行结果

0->NULL 0->1->NULL 0->1->2->NULL 0->1->2->3->NULL 0->1->2->3->4->NULL 0->1->2->666->3->4->NULL 0->1->2->666->3->4->777->NULL 0->1->2->666->888->4->777->NULL 4 0 777 false 0->1->2->666->888->4->NULL 0->1->2->666->4->NULL 1->2->666->4->NULL 1->2->666->NULL 1->666->NULL 666

  • 双向链表的封装

实现类

public class MutualLinkedList<T> implements List<T> {
    @AllArgsConstructor
    @NoArgsConstructor
    @Data
    private class Node {
        private T element;
        private Node prev;
        private Node next;

        public Node(T element) {
            this(element,null,null);
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }

    private Node dummyHead;
    private Node tail;
    private int size;

    public MutualLinkedList() {
        dummyHead = new Node();
        tail = null;
        size = 0;
    }
    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void addFirst(T value) {
        add(0,value);
    }

    @Override
    public void add(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加错误,非法索引");
        }
        if (index <= size / 2 + 1) {
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.getNext();
            }
            Node node = new Node(value,prev,prev.getNext());
            if (prev.getNext() != null) {
                prev.getNext().setPrev(node);
            }else {
                tail = node;
            }
            prev.setNext(node);
        }else {
            if (index == size) {
                addLast(value);
                return;
            } else {
                Node cur = tail;
                for (int i = size; i > index + 1; i--) {
                    cur = cur.getPrev();
                }
                Node node = new Node(value, cur.getPrev(), cur);
                cur.getPrev().setNext(node);
                cur.setPrev(node);
            }
        }
        size++;
    }

    @Override
    public void addLast(T value) {
        Node node = new Node(value,tail,tail.getNext());
        tail.setNext(node);
        tail = node;
        size++;
    }

    @Override
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("获取错误,非法索引");
        }
        if (index <= size / 2) {
            Node cur = dummyHead.getNext();
            for (int i = 0;i < index;i++) {
                cur = cur.getNext();
            }
            return cur.getElement();
        }else {
            Node cur = tail;
            for (int i = size;i > index + 1;i--) {
                cur = cur.getPrev();
            }
            return cur.getElement();
        }
    }

    @Override
    public T getFirst() {
        return get(0);
    }

    @Override
    public T getLast() {
        return tail.getElement();
    }

    @Override
    public void set(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("设置错误,非法索引");
        }
        if (index <= size / 2) {
            Node cur = dummyHead.getNext();
            for (int i = 0;i < index;i++) {
                cur = cur.getNext();
            }
            cur.setElement(value);
        }else {
            Node cur = tail;
            for (int i = size;i > index + 1;i--) {
                cur = cur.getPrev();
            }
            cur.setElement(value);
        }
    }

    @Override
    public boolean contains(T value) {
        Node cur = dummyHead.getNext();
        while (cur != null) {
            if (cur.getElement().equals(value)) {
                return true;
            }
            cur = cur.getNext();
        }
        return false;
    }

    @Override
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("删除错误,非法索引");
        }
        if (index <= size / 2) {
            Node prev = dummyHead;
            for (int i = 0;i < index;i++) {
                prev = prev.getNext();
            }
            Node ret = prev.getNext();
            prev.setNext(ret.getNext());
            ret.getNext().setPrev(prev);
            ret.setNext(null);
            ret.setPrev(null);
            size--;
            return ret.getElement();
        }else {
            Node cur = tail;
            for (int i = size;i > index + 1;i--) {
                cur = cur.getPrev();
            }
            cur.getPrev().setNext(cur.getNext());
            if (cur.getNext() != null) {
                cur.getNext().setPrev(cur.getPrev());
            }else {
                tail = cur.getPrev();
            }
            cur.setPrev(null);
            cur.setNext(null);
            size--;
            return cur.getElement();
        }
    }

    @Override
    public T removeFirst() {
        return remove(0);
    }

    @Override
    public T removeLast() {
        Node node = tail;
        tail = tail.getPrev();
        tail.setNext(null);
        node.setPrev(null);
        size--;
        return node.getElement();
    }

    @Override
    public void removeElement(T value) {
        Node pre = dummyHead;
        while (pre.getNext() != null) {
            if (value.equals(pre.getNext().getElement())) {
                Node delNode = pre.getNext();
                pre.setNext(delNode.getNext());
                delNode.setNext(null);
                size--;
                break;
            }
            pre = pre.getNext();
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node cur = dummyHead.getNext();
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.getNext();
        }
        builder.append("NULL");
        return builder.toString();
    }
}

调用

public class ListMain {
    public static void main(String[] args) {
        List<Integer> linkedList = new MutualLinkedList<>();
        for (int i = 0;i < 5;i++) {
            linkedList.add(i,i);
            System.out.println(linkedList);
        }
        linkedList.add(3,666);
        System.out.println(linkedList);

        linkedList.addLast(777);
        System.out.println(linkedList);

        linkedList.set(4,888);
        System.out.println(linkedList);

        System.out.println(linkedList.get(5));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        System.out.println(linkedList.contains(3));

        linkedList.removeLast();
        System.out.println(linkedList);

        linkedList.remove(4);
        System.out.println(linkedList);

        linkedList.removeFirst();
        System.out.println(linkedList);

        linkedList.removeLast();
        System.out.println(linkedList);
        linkedList.removeElement(2);
        System.out.println(linkedList);
        System.out.println(linkedList.getLast());
    }
}

运行结果

0->NULL 0->1->NULL 0->1->2->NULL 0->1->2->3->NULL 0->1->2->3->4->NULL 0->1->2->666->3->4->NULL 0->1->2->666->3->4->777->NULL 0->1->2->666->888->4->777->NULL 4 0 777 false 0->1->2->666->888->4->NULL 0->1->2->666->4->NULL 1->2->666->4->NULL 1->2->666->NULL 1->666->NULL 666

MutualLinkedList各操作的时间复杂度

添加操作 O(n/2) = O(n)

addLast(value) O(1)

addFirst(value) O(1)

add(index,value) O(n/2) = O(n)

删除操作 O(n)

removeLast() O(1)

removeFirst() O(1)

remove(index) O(n/2) = O(n)

修改操作

set(index,value) O(n/2) = O(n)

查找操作 O(n)

get(index) O(n/2) = O(n)

contains(value) O(n)

根据addLast(value),addFirst(value) ,removeLast() ,removeFirst() 都是O(1)的复杂度,所以用双向链表来实现队列也是很简单的。

  • 二分搜索树的封装

二分搜索树是一种可比较大小的二叉树,它可以饱和,也可以非饱和。

接口

public interface Tree<T> {
    int getSize();
    boolean isEmpty();
    void add(T t);
    boolean contains(T t);

    /**
     * 前序遍历
     */
    void preOrder();

    /**
     * 中序遍历
     */
    void inOrder();

    /**
     * 后序遍历
     */
    void postOrder();

    /**
     * 层序遍历,又称广度遍历
     * 而前、中、后序遍历又称深度遍历
     */
    void levelOrder();

    /**
     * 查找最小元素
     * @return
     */
    T minimum();

    /**
     * 查找最大元素
     * @return
     */
    T maximum();

    /**
     * 删除最小元素
     * @return
     */
    T removeMin();

    /**
     * 删除最大元素
     * @return
     */
    T removeMax();

    /**
     * 删除任意节点
     * @return
     */
    void remove(T t);

    /**
     * 找出比t小的最大值
     * @param t
     * @return
     */
    T floor(T t);

    /**
     * 找出比t大的最小值
     * @param t
     * @return
     */
    T ceil(T t);
}

实现类

public class BST<T extends Comparable<T>> implements Tree<T> {
    @AllArgsConstructor
    @Data
    private class Node{
        private T element;
        private Node left;
        private Node right;

        public Node(T element) {
            this(element,null,null);
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(T value) {
        root = add(root,value);
    }

    private Node add(Node node,T value) {
        //递归终止条件
        if (node == null) {
            size++;
            return new Node(value);
        }
        //递归
        if (value.compareTo(node.getElement()) < 0) {
            node.setLeft(add(node.getLeft(),value));
        }else if (value.compareTo(node.getElement()) > 0) {
            node.setRight(add(node.getRight(),value));
        }
        return node;
    }

    @Override
    public boolean contains(T value) {
        return contains(root,value);
    }

    private boolean contains(Node node,T value) {
        if (node == null) {
            return false;
        }
        if (value.compareTo(node.getElement()) == 0) {
            return true;
        }else if (value.compareTo(node.getElement()) < 0) {
            return contains(node.getLeft(),value);
        }else {
            return contains(node.getRight(),value);
        }
    }

    @Override
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }

        System.out.println(node.getElement());
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }

    /**
     * 非递归前序遍历
     */
    public void preOrderNR() {
        Stack<Node> stack = new ArrayStack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.getElement());
            if (cur.getRight() != null) {
                stack.push(cur.getRight());
            }
            if (cur.getLeft() != null) {
                stack.push(cur.getLeft());
            }
        }
    }

    @Override
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.getLeft());
        System.out.println(node.getElement());
        inOrder(node.getRight());
    }

    @Override
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.getLeft());
        postOrder(node.getRight());
        System.out.println(node.getElement());
    }

    @Override
    public void levelOrder() {
        Queue<Node> queue = new LoopQueue<>();
        queue.enqueue(root);
        while (!queue.isEmpty()) {
            Node cur = queue.dequeue();
            System.out.println(cur.getElement());

            if (cur.getLeft() != null) {
                queue.enqueue(cur.getLeft());
            }
            if (cur.getRight() != null) {
                queue.enqueue(cur.getRight());
            }
        }
    }

    @Override
    public T minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        return minimum(root).getElement();
    }

    private Node minimum(Node node) {
        if (node.getLeft() == null) {
            return node;
        }
        return minimum(node.getLeft());
    }

    @Override
    public T maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        return maximum(root).getElement();
    }

    private Node maximum(Node node) {
        if (node.getRight() == null) {
            return node;
        }
        return maximum(node.getRight());
    }

    @Override
    public T removeMin() {
        T ret = minimum();
        root = removeMin(root);
        return ret;
    }

    private Node removeMin(Node node) {
        //递归的终止条件,当节点的左子树为空时,递归达到最大深度
        if (node.getLeft() == null) {
            //保存最终节点的右子树
            Node rightNode = node.getRight();
            //将最终节点分离
            node.setRight(null);
            size--;
            //将保存的右子树拼接回最终节点的父节点
            return rightNode;
        }
        //从根节点开始不断向左子树递归,并逐层返回删除后的子节点重新
        //设为上层节点的左节点
        node.setLeft(removeMin(node.getLeft()));
        return node;
    }

    @Override
    public T removeMax() {
        T ret = maximum();
        root = removeMax(root);
        return ret;
    }

    private Node removeMax(Node node) {
        if (node.getRight() == null) {
            Node leftNode = node.getLeft();
            node.setLeft(null);
            size--;
            return leftNode;
        }

        node.setRight(removeMax(node.getRight()));
        return node;
    }

    @Override
    public void remove(T value) {
        root = remove(root,value);
    }

    private Node remove(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) < 0) {
            node.setLeft(remove(node.getLeft(),value));
            return node;
        }else if (value.compareTo(node.getElement()) > 0) {
            node.setRight(remove(node.getRight(),value));
            return node;
        }else {
            //待删除节点左子树为空的情况
            if (node.getLeft() == null) {
                Node rightNode = node.getRight();
                node.setRight(null);
                size--;
                return rightNode;
            }
            //待删除节点右子树为空的情况
            if (node.getRight() == null) {
                Node leftNode = node.getLeft();
                node.setLeft(null);
                size--;
                return leftNode;
            }
            //待删除节点左右子树均不为空的情况
            //找到比待删除节点大的最小节点,即待删除节点右子树的最小节点
            //用这个节点顶替待删除节点的位置
            Node successor = minimum(node.getRight());
            successor.setRight(removeMin(node.getRight()));
            successor.setLeft(node.getLeft());
            node.setLeft(null);
            node.setRight(null);
            return successor;
            //找到比待删除节点小的最大节点,即待删除节点左子树的最大节点
            //用这个节点顶替待删除节点的位置,此二种方法取其一即可
//            Node predecessor = maximum(node.getLeft());
//            predecessor.setLeft(removeMax(node.getLeft()));
//            predecessor.setRight(node.getRight());
//            node.setLeft(null);
//            node.setRight(null);
//            return predecessor;
        }
    }

    @Override
    public T floor(T value) {
        Node node = floor(root,value);
        if (node != null) {
            return node.getElement();
        }
        return null;
    }

    private Node floor(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) <= 0) {
            return floor(node.getLeft(),value);
        }else {
            if (node.getRight() == null) {
                return node;
            }else if (node.getRight().getLeft() == null &&
                    value.compareTo(node.getRight().getElement()) <= 0) {
                return node;
            }else if (node.getRight().getRight() == null &&
                    value.compareTo(node.getRight().getElement()) > 0) {
                return node.getRight();
            }
            return floor(node.getRight(),value);
        }
    }

    @Override
    public T ceil(T value) {
        Node node = ceil(root,value);
        if (node != null) {
            return node.getElement();
        }
        return null;
    }

    private Node ceil(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) >= 0) {
            return ceil(node.getRight(),value);
        }else {
            if (node.getLeft() == null) {
                return node;
            }else if (value.compareTo(maximum(node.getLeft()).getElement()) >= 0) {
                return node;
            }else if (node.getLeft().getRight() == null &&
                    value.compareTo(node.getLeft().getElement()) >= 0) {
                return node;
            }else if (node.getLeft().getLeft() == null &&
                    value.compareTo(node.getLeft().getElement()) < 0) {
                return node.getLeft();
            }
            return ceil(node.getLeft(),value);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        generateBSTString(root,0,builder);
        return builder.toString();
    }

    private void generateBSTString(Node node,int depth,StringBuilder builder) {
        if (node == null) {
            builder.append(generateDepthString(depth) + "null\n");
            return;
        }
        builder.append(generateDepthString(depth) + node.getElement() + "\n");
        generateBSTString(node.getLeft(),depth + 1,builder);
        generateBSTString(node.getRight(),depth + 1,builder);
    }

    private String generateDepthString(int depth) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i < depth;i++) {
            builder.append("--");
        }
        return builder.toString();
    }
}

调用

public class TreeMain {
    public static void main(String[] args) {
        Tree<Integer> bst = new BST<>();
        Integer[] nums = {50,30,60,80,40,20};
        Stream.of(nums).forEach(bst::add);
        System.out.println("递归前序遍历");
        bst.preOrder();
        System.out.println("非递归前序遍历");
        ((BST)bst).preOrderNR();
        ///////////////////////////////
        //            50              //
        //           / \             //
        //          30  60            //
        //         / \   \           //
        //        20  40  80          //
        ///////////////////////////////
        System.out.println("中序遍历");
        bst.inOrder();
        System.out.println("后续遍历");
        bst.postOrder();
        System.out.println("层序遍历");
        bst.levelOrder();
        System.out.println();
        System.out.println(bst);
        System.out.println(bst.floor(35));
        System.out.println(bst.ceil(45));
        System.out.println();
        bst.remove(30);
        System.out.println(bst);
    }
}

运行结果

递归前序遍历 50 30 20 40 60 80 非递归前序遍历 50 30 20 40 60 80 中序遍历 20 30 40 50 60 80 后续遍历 20 40 30 80 60 50 层序遍历 50 30 60 20 40 80

50 --30 ----20 ------null ------null ----40 ------null ------null --60 ----null ----80 ------null ------null

30 50

50 --40 ----20 ------null ------null ----null --60 ----null ----80 ------null ------null

对删除最小,最大元素进行测试

public class TreeMain1 {
    public static void main(String[] args) {
        Tree<Integer> bst = new BST<>();
        Random random = new Random();
        for (int i = 0;i < 1000;i++) {
            bst.add(random.nextInt(10000));
        }
        Array<Integer> numsMin = new DefaultArray<>();
        while (!bst.isEmpty()) {
            numsMin.addLast(bst.removeMin());
        }
        System.out.println(numsMin);
        for (int i = 1;i < numsMin.getSize();i++) {
            if (numsMin.get(i - 1) > numsMin.get(i)) {
                throw new IllegalArgumentException("错误");
            }
        }
        System.out.println("removeMin测试成功");

        for (int i = 0;i < 1000;i++) {
            bst.add(random.nextInt(10000));
        }
        Array<Integer> numsMax = new DefaultArray<>();
        while (!bst.isEmpty()) {
            numsMax.addLast(bst.removeMax());
        }
        System.out.println(numsMax);
        for (int i = 1;i < numsMax.getSize();i++) {
            if (numsMax.get(i - 1) < numsMax.get(i)) {
                throw new IllegalArgumentException("错误");
            }
        }
        System.out.println("removeMax测试成功");
    }
}

运行结果

DefaultArray(data=[1,8,9,21,25,36,69,77,88,89,109,116,121,132,135,146,168,211,220,238,242,249,254,296,304,314,316,320,353,364,380,391,395,399,402,409,416,421,425,426,450,457,463,473,478,491,519,534,543,545,563,573,579,581,590,591,600,644,648,655,661,670,697,710,712,713,717,724,734,739,744,750,754,787,803,812,813,824,835,838,841,843,844,867,869,882,907,912,933,937,940,943,952,959,970,972,974,988,991,996,1000,1004,1019,1031,1032,1040,1064,1069,1085,1117,1120,1122,1131,1148,1151,1154,1174,1226,1232,1233,1234,1235,1243,1246,1283,1291,1301,1327,1338,1340,1389,1395,1403,1411,1416,1420,1424,1434,1440,1447,1450,1459,1461,1471,1474,1493,1495,1497,1499,1510,1521,1528,1533,1537,1549,1564,1569,1585,1586,1608,1613,1621,1644,1670,1672,1674,1677,1699,1713,1717,1739,1754,1756,1763,1783,1786,1795,1797,1814,1819,1828,1843,1850,1855,1866,1875,1894,1897,1902,1913,1918,1925,1952,1995,1998,2014,2025,2027,2041,2045,2046,2059,2071,2074,2079,2102,2118,2120,2132,2139,2155,2156,2163,2165,2170,2193,2194,2205,2209,2234,2238,2266,2267,2272,2273,2277,2282,2302,2313,2331,2353,2360,2370,2380,2390,2416,2435,2439,2449,2454,2475,2478,2502,2514,2521,2522,2543,2568,2578,2590,2612,2617,2646,2662,2663,2665,2667,2677,2683,2687,2688,2691,2708,2711,2716,2751,2783,2794,2813,2817,2826,2853,2866,2879,2883,2885,2899,2914,2921,2926,2933,3003,3007,3020,3048,3059,3080,3083,3105,3108,3142,3150,3162,3218,3226,3230,3249,3258,3268,3285,3287,3293,3305,3322,3323,3340,3356,3372,3379,3386,3394,3412,3417,3433,3441,3451,3460,3483,3509,3511,3518,3534,3542,3561,3567,3584,3593,3599,3609,3618,3627,3632,3647,3659,3668,3670,3675,3676,3695,3697,3706,3712,3738,3754,3756,3765,3771,3801,3812,3820,3823,3834,3841,3846,3848,3853,3857,3866,3896,3906,3910,3915,3943,3949,3960,3971,3984,3990,4010,4024,4027,4030,4033,4059,4079,4080,4090,4104,4111,4122,4135,4138,4146,4150,4151,4169,4176,4193,4194,4202,4206,4207,4211,4216,4226,4243,4244,4251,4264,4269,4272,4292,4301,4305,4315,4322,4342,4352,4362,4383,4397,4398,4412,4414,4417,4430,4458,4474,4487,4490,4506,4564,4583,4587,4608,4622,4632,4642,4643,4652,4654,4665,4673,4674,4676,4699,4706,4707,4714,4722,4730,4732,4758,4759,4765,4788,4842,4850,4851,4856,4880,4887,4891,4892,4893,4897,4903,4905,4926,4949,4969,4972,4978,4979,4984,5037,5050,5059,5060,5079,5087,5122,5141,5145,5154,5183,5184,5193,5201,5215,5227,5229,5231,5241,5252,5259,5267,5315,5323,5331,5339,5343,5344,5357,5359,5397,5403,5405,5410,5412,5416,5417,5419,5444,5446,5465,5489,5490,5493,5504,5506,5510,5524,5536,5545,5552,5557,5563,5577,5586,5587,5590,5607,5615,5632,5674,5684,5698,5699,5719,5721,5726,5727,5739,5747,5749,5753,5762,5774,5776,5796,5815,5822,5836,5840,5848,5856,5861,5882,5896,5899,5911,5913,5916,5932,5945,5965,5968,5972,5982,5994,6014,6023,6032,6050,6076,6084,6116,6119,6120,6130,6131,6140,6145,6150,6154,6162,6169,6173,6187,6191,6195,6253,6260,6277,6295,6300,6304,6306,6318,6325,6336,6337,6343,6356,6362,6378,6383,6392,6404,6416,6428,6460,6492,6534,6555,6560,6571,6574,6580,6582,6590,6593,6597,6605,6608,6611,6615,6626,6636,6641,6649,6652,6659,6662,6672,6676,6686,6691,6712,6753,6773,6779,6781,6782,6789,6790,6807,6808,6817,6842,6849,6852,6863,6869,6885,6886,6892,6896,6899,6906,6925,6937,6950,6957,6960,6970,6994,7019,7027,7043,7045,7054,7064,7083,7096,7098,7100,7125,7136,7160,7163,7190,7193,7228,7229,7236,7239,7248,7249,7253,7254,7265,7280,7281,7291,7330,7335,7344,7346,7348,7386,7391,7394,7395,7407,7418,7423,7428,7443,7448,7450,7454,7457,7465,7475,7479,7484,7488,7491,7492,7496,7501,7515,7520,7538,7579,7581,7588,7592,7595,7611,7619,7634,7641,7682,7703,7704,7720,7733,7737,7765,7773,7778,7789,7794,7800,7814,7827,7835,7898,7909,7916,7934,7940,7952,7957,7963,7966,7970,7978,7981,7989,8008,8025,8030,8033,8034,8039,8049,8059,8070,8077,8078,8080,8081,8090,8092,8127,8130,8132,8156,8162,8165,8177,8183,8190,8193,8212,8216,8219,8229,8246,8250,8258,8261,8279,8303,8321,8337,8339,8347,8378,8388,8419,8427,8428,8433,8456,8458,8462,8463,8481,8483,8485,8493,8494,8503,8511,8513,8533,8557,8560,8571,8585,8588,8626,8627,8628,8633,8661,8671,8675,8679,8686,8692,8716,8721,8722,8723,8730,8745,8777,8815,8833,8834,8837,8855,8863,8881,8890,8914,8915,8925,8935,8962,8988,9005,9031,9040,9060,9066,9077,9078,9113,9118,9130,9131,9133,9135,9154,9160,9165,9166,9167,9170,9175,9185,9190,9203,9218,9219,9227,9231,9232,9233,9253,9261,9265,9273,9279,9286,9292,9299,9303,9306,9335,9345,9352,9362,9392,9397,9410,9411,9413,9436,9461,9470,9477,9486,9515,9520,9526,9533,9554,9560,9574,9581,9584,9596,9606,9608,9609,9614,9619,9631,9640,9652,9653,9663,9664,9717,9742,9756,9760,9771,9776,9790,9793,9835,9852,9853,9861,9880,9883,9889,9909,9918,9919,9937,9941,9945,9947,9960,9975,9978,9982,9996], size=948 removeMin测试成功 DefaultArray(data=[9985,9960,9946,9943,9940,9933,9931,9919,9911,9906,9905,9903,9896,9882,9867,9866,9849,9840,9824,9823,9820,9817,9814,9813,9774,9770,9764,9763,9734,9698,9692,9688,9677,9675,9670,9662,9653,9645,9612,9591,9582,9581,9554,9548,9542,9520,9515,9492,9468,9439,9420,9419,9415,9400,9385,9383,9372,9345,9330,9318,9295,9278,9268,9267,9263,9256,9210,9208,9206,9197,9192,9191,9164,9154,9151,9147,9145,9124,9117,9098,9084,9074,9068,9064,9034,9028,9024,9021,8967,8950,8946,8907,8903,8884,8880,8876,8872,8869,8865,8852,8850,8839,8838,8827,8825,8821,8807,8806,8804,8803,8796,8791,8782,8776,8756,8753,8744,8728,8727,8726,8709,8704,8702,8693,8685,8684,8673,8668,8653,8604,8600,8580,8579,8562,8552,8548,8547,8532,8531,8523,8522,8518,8509,8488,8453,8427,8424,8409,8400,8384,8369,8356,8350,8341,8322,8317,8290,8284,8280,8266,8260,8255,8250,8231,8202,8196,8191,8190,8173,8143,8129,8117,8096,8094,8092,8066,8052,8046,8037,8036,8024,8021,8012,8006,7994,7991,7982,7981,7967,7956,7951,7946,7921,7916,7876,7869,7864,7862,7852,7838,7837,7835,7833,7825,7824,7821,7807,7790,7736,7717,7715,7706,7691,7686,7676,7675,7663,7641,7637,7635,7615,7606,7596,7591,7587,7569,7540,7529,7513,7509,7508,7507,7491,7485,7480,7475,7470,7460,7429,7426,7425,7401,7400,7379,7372,7363,7344,7343,7339,7307,7306,7295,7290,7287,7283,7276,7256,7224,7223,7220,7203,7199,7192,7172,7168,7167,7164,7155,7144,7143,7137,7124,7086,7082,7072,7058,7044,7025,7023,7022,7018,7003,6998,6996,6989,6985,6971,6965,6958,6937,6932,6926,6913,6910,6909,6906,6894,6892,6862,6848,6839,6837,6836,6832,6824,6823,6821,6812,6787,6776,6771,6763,6749,6748,6745,6736,6725,6723,6717,6714,6711,6688,6672,6653,6649,6640,6635,6625,6623,6617,6612,6611,6600,6594,6546,6544,6537,6522,6520,6500,6490,6473,6451,6444,6441,6437,6436,6417,6405,6370,6366,6361,6359,6358,6355,6333,6326,6309,6302,6285,6265,6248,6235,6234,6224,6219,6216,6209,6196,6182,6174,6169,6168,6165,6153,6147,6141,6139,6131,6121,6095,6071,6047,6038,6027,6025,6018,6012,5975,5970,5965,5964,5959,5957,5930,5926,5920,5914,5911,5907,5902,5900,5891,5868,5848,5807,5774,5768,5758,5748,5736,5684,5682,5669,5665,5660,5644,5640,5639,5637,5636,5634,5616,5606,5586,5585,5566,5553,5535,5527,5524,5514,5496,5488,5480,5455,5450,5446,5442,5420,5369,5367,5363,5356,5320,5317,5293,5279,5247,5237,5231,5216,5208,5206,5184,5180,5168,5159,5144,5137,5123,5091,5088,5085,5084,5081,5067,5061,5026,5015,5007,5002,4992,4986,4980,4976,4975,4946,4945,4935,4934,4932,4926,4922,4912,4895,4890,4886,4872,4870,4844,4831,4795,4790,4786,4766,4756,4753,4738,4737,4721,4717,4711,4709,4693,4682,4674,4669,4668,4619,4615,4591,4590,4587,4586,4583,4581,4553,4547,4544,4541,4540,4526,4515,4501,4475,4468,4453,4411,4402,4391,4384,4361,4355,4354,4338,4331,4323,4321,4318,4315,4311,4307,4274,4270,4268,4264,4263,4253,4248,4232,4226,4225,4223,4203,4192,4166,4158,4152,4148,4127,4091,4080,4079,4076,4038,4037,4026,4013,3996,3985,3969,3956,3950,3939,3938,3936,3930,3906,3897,3876,3868,3851,3844,3843,3816,3802,3801,3799,3782,3781,3780,3774,3767,3765,3764,3753,3750,3749,3741,3731,3729,3722,3715,3706,3697,3665,3664,3657,3647,3625,3624,3623,3609,3599,3594,3574,3571,3554,3552,3548,3542,3531,3519,3508,3479,3472,3464,3451,3449,3444,3436,3427,3420,3417,3416,3366,3358,3329,3321,3318,3316,3289,3257,3246,3243,3221,3210,3206,3201,3192,3161,3149,3132,3121,3115,3106,3093,3090,3077,3075,3064,3063,3050,3041,3021,3019,3017,3014,3008,2999,2964,2953,2942,2904,2903,2894,2871,2862,2854,2853,2836,2826,2795,2788,2773,2765,2763,2748,2730,2714,2703,2695,2652,2650,2637,2636,2622,2621,2603,2591,2581,2579,2576,2575,2571,2563,2551,2543,2535,2524,2513,2500,2491,2490,2482,2467,2464,2462,2455,2454,2448,2431,2427,2424,2383,2370,2356,2352,2329,2311,2303,2283,2273,2271,2269,2251,2249,2203,2201,2195,2177,2175,2161,2151,2142,2135,2120,2110,2100,2094,2087,2082,2078,2077,2070,2063,2055,2050,2032,2027,2026,2009,2001,1955,1944,1941,1938,1923,1912,1890,1878,1877,1871,1865,1859,1844,1830,1827,1824,1799,1798,1795,1779,1769,1762,1728,1709,1706,1703,1700,1687,1660,1622,1616,1610,1593,1559,1540,1533,1532,1524,1513,1506,1492,1486,1467,1457,1433,1423,1413,1387,1384,1375,1366,1360,1358,1357,1342,1331,1320,1309,1307,1304,1296,1295,1259,1227,1222,1205,1193,1182,1165,1141,1130,1125,1123,1118,1107,1103,1098,1088,1080,1065,1063,1059,1027,1019,998,978,959,958,946,941,938,931,927,908,907,901,898,895,890,883,869,859,858,848,843,836,831,810,802,775,758,751,737,735,729,728,721,706,702,683,670,640,629,620,584,554,548,542,538,537,521,503,501,487,484,478,477,476,449,441,427,424,416,400,393,377,367,358,346,323,310,293,292,280,274,263,251,244,235,224,219,205,190,176,175,154,149,138,134,125,118,109,105,102,99,96,93,85,77,74,64,41,37,10,2], size=949 removeMax测试成功

  • 二分搜索树集合的封装

集合是一种不包含重复元素的数据结构

接口

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

实现类

public class BSTSet<T extends Comparable<T>> implements Set<T> {
    private Tree<T> bst;

    public BSTSet() {
        bst = new BST<>();
    }
    @Override
    public void add(T value) {
        bst.add(value);
    }

    @Override
    public void remove(T value) {
        bst.remove(value);
    }

    @Override
    public boolean contains(T value) {
        return bst.contains(value);
    }

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

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

调用

我们会先从一本《傲慢与偏见》的英文电子书中读出多少个单词,然后放入集合中,查看有多少不重复的单词。

文件读取

public class FileOperation {
    /**
     * 读取文件名称为filename中的内容,并将其中包含的所有词语放进words中
     * @param filename
     * @param words
     * @return
     */
    public static boolean readFile(String filename, Array<String> words) {
        if (filename == null || words == null) {
            System.out.println("filename为空或words为空");
            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 (FileNotFoundException e) {
            System.out.println("无法打开" + 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.addLast(word);
                    start = firstCharacterIndex(contents,i);
                    i = start + 1;
                }else {
                    i++;
                }
            }
        }
        return true;

    }

    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();
    }
}

测试

public class SetMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Set<String> set = new BSTSet<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(set::add);
        System.out.println("共有不同的单词: " + set.getSize());
    }
}

运行结果

傲慢与偏见 共有单词: 125901 共有不同的单词: 6530

  • 链表集合的封装

实现类(以下的List和LinkedList皆为之前自主实现的链表封装而非JDK的List接口和LinkedList的实现类)

public class LinkedListSet<T> implements Set<T> {
    private List<T> list;

    public LinkedListSet() {
        list = new LinkedList<>();
    }
    @Override
    public void add(T value) {
        if (!list.contains(value)) {
            list.addFirst(value);
        }
    }

    @Override
    public void remove(T value) {
        list.removeElement(value);
    }

    @Override
    public boolean contains(T value) {
        return list.contains(value);
    }

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

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

调用

public class SetMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Set<String> set = new LinkedListSet<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(set::add);
        System.out.println("共有不同的单词: " + set.getSize());
    }
}

运行结果

傲慢与偏见 共有单词: 125901 共有不同的单词: 6530

虽然运行结果相同,但我们能明显感觉到在获取不同的单词的时候,运行时间明显偏长。

两种集合的性能测试

public class TestSetMain {
    private static double testSet(Set<String> set,String filename) {
        long startTime = System.nanoTime();
        System.out.println(filename);
        Array<String> words = new DefaultArray<>();
        if (FileOperation.readFile(filename,words)) {
            System.out.println("共有单词: " + words.getSize());
            Stream.of(words.getData()).filter(data -> data != null)
                    .forEach(set::add);
            System.out.println("共有不同单词: " + set.getSize());
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        String filename = "/Users/admin/Downloads/pride-and-prejudice.txt";
        Set<String> bstSet = new BSTSet<>();
        double time1 = testSet(bstSet,filename);
        System.out.println("BST Set: " + time1 + " s");
        System.out.println();
        Set<String> linkedListSet = new LinkedListSet<>();
        double time2 = testSet(linkedListSet,filename);
        System.out.println("LinkedList Set: " + time2 + " s");
    }
}

测试结果

/Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同单词: 6530 BST Set: 0.140089974 s

/Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同单词: 6530 LinkedList Set: 2.184659522 s

对于LinkedListSet操作的时间复杂度

add(value) O(n)

contains(value) O(n)

remove(value) O(n)

对于BSTSet操作的时间复杂度

add(value) O(h)

contains(value) O(h)

remove(value) O(h)

以上h为二分搜索树的高度。现在我们来看一下h与n的关系是什么。假设一颗二分搜索树是饱和的,如下图所示

假设该二分搜索树共h层

则0层的节点数为 1

1层的节点数为 2

2层的节点数为 4

3层的节点数为 8

4层的节点数为 16

h-1层的节点数为 2^(h-1)

则总节点数 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4+ …… + 2^(h-1),我们可以看到这是一个等比数列,它的公比为2。根据等比数列的求和公式

可得(q为底数,此时q为2;a1为常数,此时a1为1;n为层数,此时为h),关于该公式的推导可以参考https://www.iqiyi.com/w_19rr8796p1.html ,最后可得

最后可得总节点数n = 2^h - 1,则h = log2(n + 1),其中红色2为底数。

省略掉常数和底数,最后得到二分搜索树的时间复杂度为O(log n)

对于BSTSet操作的时间复杂度可以改为

add(value) O(log n)

contains(value) O(log n)

remove(value) O(log n)

我们来直观的看一下log n和线性复杂度n的增长情况

log n n

n = 16 4 16 相差4倍

n = 1024 10 1024 相差100倍

n = 100万 20 100万 相差5万倍

以上我们是根据满二分搜索树来推断的,但二分搜索树也有一种最坏的情况,就是它的高度等于它的节点数(h == n),这样它就退化成了一个链表,这样它的时间复杂度就是O(n)而不是O(log n)了。

LeetCode算法题 https://leetcode-cn.com/problems/unique-morse-code-words/

这是LeetCode的804题——唯一摩尔斯密码词

我们先用JDK的TreeSet来完成。该类是实现了红黑树为底层的集合。(此处的Set为java.util.Set,TreeSet为java.util.TreeSet)

public class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        Set<String> set = new TreeSet<>();
        Stream.of(words).forEach(word -> {
            StringBuilder builder = new StringBuilder();
            for (int i = 0;i < word.length();i++) {
                builder.append(codes[word.charAt(i) - 'a']);
            }
            set.add(builder.toString());
        });
        return set.size();
    }
}

提交给LeetCode

  • 链表映射封装

映射是一种表示key,value键值对的数据结构

接口

public interface Map<K,V> {
    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();
    boolean isEmpty();
}

实现类

由于映射有两个泛型,所以之前实现的LinkedList将不再复用。

public class LinkedListMap<K,V> implements Map<K,V> {
    @AllArgsConstructor
    @Data
    @NoArgsConstructor
    private class Node {
        private K key;
        private V value;
        private Node next;

        public Node(K key) {
            this(key,null,null);
        }

        public Node(K key,V value) {
            this(key,value,null);
        }

        @Override
        public String toString() {
            return key.toString() + " : " + value.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedListMap() {
        dummyHead = new Node();
        size = 0;
    }

    @Override
    public void add(K key, V value) {
        Node node = getNode(key);
        if (node == null) {
            dummyHead.setNext(new Node(key,value,dummyHead.getNext()));
            size++;
        }else {
            node.setValue(value);
        }
    }

    @Override
    public V remove(K key) {
        Node pre = dummyHead;
        while (pre.getNext() != null) {
            if (key.equals(pre.getNext().getKey())) {
                Node delNode = pre.getNext();
                pre.setNext(delNode.getNext());
                delNode.setNext(null);
                size--;
                return delNode.getValue();
            }
            pre = pre.getNext();
        }
        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.getValue();
    }

    @Override
    public void set(K key, V value) {
        Node node = getNode(key);
        if (node == null) {
            throw new IllegalArgumentException(key + "不存在");
        }
        node.setValue(value);
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private Node getNode(K key) {
        Node cur = dummyHead.getNext();
        while (cur != null) {
            if (key.equals(cur.getKey())) {
                return cur;
            }
            cur = cur.getNext();
        }
        return null;
    }
}

调用

public class MapMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Map<String,Integer> map = new LinkedListMap<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
    }
}

运行结果(时间较慢)

傲慢与偏见 共有单词: 125901 共有不同的单词: 6530 pride出现的次数: 53 prejudice出现的次数: 11

  • 二分搜索树映射封装

由于映射有两个泛型,所以之前实现的BST将不再复用

实现类

public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> {
    @Data
    @AllArgsConstructor
    private class Node{
        private K key;
        private V value;
        private Node left;
        private Node right;

        public Node(K key) {
            this(key,null,null,null);
        }
        public Node(K key,V value) {
            this(key,value,null,null);
        }
    }

    private Node root;
    private int size;

    public BSTMap() {
        root = null;
        size = 0;
    }
    @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.getKey()) < 0) {
            node.setLeft(add(node.getLeft(),key,value));
        }else if (key.compareTo(node.getKey()) > 0) {
            node.setRight(add(node.getRight(),key,value));
        }else {
            node.setValue(value);
        }
        return node;
    }

    @Override
    public V remove(K key) {
        Node node = getNode(root,key);
        if (node != null) {
            root = remove(root,key);
            return node.getValue();
        }
        return null;
    }

    private Node remove(Node node,K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.getKey()) < 0) {
            node.setLeft(remove(node.getLeft(),key));
            return node;
        }else if (key.compareTo(node.getKey()) > 0) {
            node.setRight(remove(node.getRight(),key));
            return node;
        }else {
            //待删除节点左子树为空的情况
            if (node.getLeft() == null) {
                Node rightNode = node.getRight();
                node.setRight(null);
                size--;
                return rightNode;
            }
            //待删除节点右子树为空的情况
            if (node.getRight() == null) {
                Node leftNode = node.getLeft();
                node.setLeft(null);
                size--;
                return leftNode;
            }
            //待删除节点左右子树均不为空的情况
            //找到比待删除节点大的最小节点,即待删除节点右子树的最小节点
            //用这个节点顶替待删除节点的位置
            Node successor = minimum(node.getRight());
            successor.setRight(removeMin(node.getRight()));
            successor.setLeft(node.getLeft());
            node.setLeft(null);
            node.setRight(null);
            return successor;
        }
    }

    private Node minimum(Node node) {
        if (node.getLeft() == null) {
            return node;
        }
        return minimum(node.getLeft());
    }

    private Node removeMin(Node node) {
        if (node.getLeft() == null) {
            Node rightNode = node.getRight();
            node.setRight(null);
            size--;
            return rightNode;
        }
        node.setLeft(removeMin(node.getLeft()));
        return node;
    }

    @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.getValue();
    }

    @Override
    public void set(K key, V value) {
        Node node = getNode(root,key);
        if (node == null) {
            throw new IllegalArgumentException(key + "不存在");
        }
        node.setValue(value);
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private Node getNode(Node node,K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.getKey()) == 0) {
            return node;
        }else if (key.compareTo(node.getKey()) < 0) {
            return getNode(node.getLeft(),key);
        }else {
            return getNode(node.getRight(),key);
        }
    }
}

调用

public class MapMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Map<String,Integer> map = new BSTMap<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
    }
}

运行结果(时间较快)

傲慢与偏见 共有单词: 125901 共有不同的单词: 6530 pride出现的次数: 53 prejudice出现的次数: 11

两种映射的性能测试

public class TestMapMain {
    private static double testMap(Map<String,Integer> map,String filename) {
        long startTime = System.nanoTime();
        System.out.println(filename);
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile(filename,words);
        System.out.println("共有单词: " + words.getSize());
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        String filename = "/Users/admin/Downloads/pride-and-prejudice.txt";
        Map<String,Integer> bstMap = new BSTMap<>();
        double time1 = testMap(bstMap,filename);
        System.out.println("BST Map: " + time1 + " s");

        Map<String,Integer> linkedListMap = new LinkedListMap<>();
        double time2 = testMap(linkedListMap,filename);
        System.out.println("LinkedList Map: " + time2 + " s");
    }
}

测试结果

/Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同的单词: 6530 pride出现的次数: 53 prejudice出现的次数: 11 BST Map: 0.178329962 s /Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同的单词: 6530 pride出现的次数: 53 prejudice出现的次数: 11 LinkedList Map: 9.18811603 s

对于LinkedListMap各操作的时间复杂度

add(key,value) O(n)

remove(key) O(n)

contains(key) O(n)

get(key) O(n)

set(key,value) O(n)

对于BSTMap各操作的时间复杂度

add(key,value) O(log n) 平均 O(n) 最差

remove(key) O(log n) 平均 O(n) 最差

contains(key) O(log n) 平均 O(n) 最差

get(key) O(log n) 平均 O(n) 最差

set(key,value) O(log n) 平均 O(n) 最差

LeetCode算法题 https://leetcode-cn.com/problems/intersection-of-two-arrays/

这是LeetCode的第349题——两个数组的交集

我们先用JDK的TreeSet来完成。该类是实现了红黑树为底层的集合。(此处的Set为java.util.Set,TreeSet为java.util.TreeSet,List为java.util.List,ArrayList为java.util.ArrayList)

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new TreeSet<>();
        for (int num : nums1) {
            set.add(num);
        }
        List<Integer> list = new ArrayList<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                list.add(num);
                set.remove(num);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0;i < list.size();i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

提交给LeetCode

LeetCode算法题 https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

这是LeetCode的350题——两个数组的交集II

我们先用JDK的TreeMap来完成,该类是实现了红黑树为底层的映射。(此处的Map为java.util.Map,TreeMap为java.util.TreeMap,List为java.util.List,ArrayList为java.util.ArrayList)

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new TreeMap<>();
        for (int num : nums1) {
            if (map.putIfAbsent(num,1) != null) {
                map.put(num,map.get(num) + 1);
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int num : nums2) {
            if (map.containsKey(num)) {
                list.add(num);
                map.put(num,map.get(num) - 1);
                if (map.get(num) == 0) {
                    map.remove(num);
                }
            }
        }
        int[] ret = new int[list.size()];
        for (int i = 0;i < list.size();i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}

提交到LeetCode

  • 最大堆封装

堆是一种完全二叉树,完全二叉树就是从根节点依次向下层,每一层从左到右依次填充元素的二叉树。完全二叉树可以不是满二叉树。而最大堆的特性是某个节点的值总是不大于其父节点的值。

类似于上图这种就是一个最大堆,它同时满足了完全二叉树的特性。在最大堆中,并不是说上层的节点值一定比下层的节点值要大,而是每一个节点值不比其父节点大。由于其依次填充性,我们也可以用数组来看待这个最大堆。所以我们可以用数组来做最大堆的底层实现,二叉树中父节点,左右子节点的索引关系可以表示为:已知一个节点的索引i(无论它是左节点还是右节点),它的父节点的索引为 (根节点的索引为0)

parent(i) = (i - 1) / 2

已知一个父节点的索引i,其左右子节点的索引为

left child = 2 * i + 1

right child = 2 * i + 2

接口

public interface Heap<T> {
    int getSize();
    boolean isEmpty();
    void add(T t);

    /**
     * 取出最大元素(最大堆)或最小元素(最小堆)
     * @return
     */
    T extract();

    /**
     * 查看最大元素(最大堆)或最小元素(最小堆)
     * @return
     */
    T findHeap();

    /**
     * 取出堆中最大元素(最大堆)或最小元素(最小堆)
     * 并且替换成元素t
     * @param t
     * @return
     */
    T replace(T t);
}

实现类

public class MaxHeap<T extends Comparable<T>> implements Heap<T> {
    private Array<T> data;

    public MaxHeap(int capacity) {
        data = new DefaultArray<>(capacity);
    }

    public MaxHeap() {
        data = new DefaultArray<>();
    }

    /**
     * 将任意一个数组转化成最大堆,此种方式称为Heapify
     * 过程为先找到非叶节点的最后一个节点,依次向根节点遍历,
     * 将每一个节点浮动下沉,即可完成任意数组向最大堆的转化
     * 找最后一个非叶节点的方法即为找到最后一个叶节点(数组的最后一个索引size-1)
     * 的父节点
     * 将n个元素逐一插入到一个空堆中,时间复杂度为O(nlog n)
     * heapify的过程,时间复杂度为O(n)
     * @param arr
     */
    public MaxHeap(T[] arr) {
        data = new DefaultArray<>(arr);
        for (int i = parent(getSize() - 1);i >= 0;i--) {
            siftDown(i);
        }
    }

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

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

    @Override
    public void add(T value) {
        data.addLast(value);
        siftUp(data.getSize() - 1);
    }

    /**
     * 堆节点浮动上移
     * @param index
     */
    private void siftUp(int index) {
        while (index > 0 &&
                data.get(parent(index)).compareTo(data.get(index)) < 0) {
            data.swap(index,parent(index));
            index = parent(index);
        }
    }

    @Override
    public T extract() {
        T ret = findHeap();
        data.swap(0,data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    /**
     * 堆节点浮动下沉
     * @param index
     */
    private void siftDown(int index) {
        while (leftChild(index) < data.getSize()) {
            int j = leftChild(index);
            if (j + 1 < data.getSize() &&
                    data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChile(index);
            }
            //data[j]是左右孩子的最大值
            if (data.get(index).compareTo(data.get(j)) >= 0) {
                break;
            }
            data.swap(index,j);
            index = j;
        }
    }

    @Override
    public T findHeap() {
        if (isEmpty()) {
            throw new IllegalArgumentException("堆为空,不能做此操作");
        }
        return data.get(0);
    }

    @Override
    public T replace(T value) {
        T ret = findHeap();
        data.set(0,value);
        siftDown(0);
        return ret;
    }

    /**
     * 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
     * @param index
     * @return
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("索引0没有父节点");
        }
        return (index - 1) / 2;
    }

    /**
     * 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
     * @param index
     * @return
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
     * @param index
     * @return
     */
    private int rightChile(int index) {
        return index * 2 + 2;
    }
}

调用

public class HeapMain {
    public static void main(String[] args) {
        int n = 1000000;
        Heap<Integer> maxHeap = new MaxHeap<>();
        Random random = new Random();
        for (int i = 0;i < n;i++) {
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
        }
        int[] arr = new int[n];
        for (int i = 0;i < n;i++) {
            arr[i] = maxHeap.extract();
        }
        for (int i = 1;i < n;i++) {
            if (arr[i - 1] < arr[i]) {
                throw new IllegalArgumentException("出错");
            }
        }
        System.out.println("测试最大堆完成");
    }
}

运行结果

测试最大堆完成

对Heapify和非Heapify两种数组转化最大堆的测试

public class TestHeapMain {
    private static double testHeap(Integer[] testData,boolean isHeapify) {
        long startTime = System.nanoTime();
        Heap<Integer> maxHeap;
        if (isHeapify) {
            maxHeap = new MaxHeap<>(testData);
        }else {
            maxHeap = new MaxHeap<>();
            Stream.of(testData).forEach(maxHeap::add);
        }
        int[] arr = new int[testData.length];
        for (int i = 0;i < testData.length;i++) {
            arr[i] = maxHeap.extract();
        }
        for (int i = 1;i < testData.length;i++) {
            if (arr[i - 1] < arr[i]) {
                throw new IllegalArgumentException("错误");
            }
        }
        System.out.println("测试最大堆成功");
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int n = 1000000;
        Random random = new Random();
        Integer[] testData = new Integer[n];
        for (int i = 0;i < n;i++) {
            testData[i] = random.nextInt(Integer.MAX_VALUE);
        }
        double time1 = testHeap(testData,false);
        System.out.println("不使用heapify: " + time1 + " s");
        System.out.println();
        double time2 = testHeap(testData,true);
        System.out.println("使用heapify: " + time2 + " s");
    }
}

测试结果

测试最大堆成功 不使用heapify: 0.876574063 s

测试最大堆成功 使用heapify: 0.496209799 s

  • 优先队列封装

实现类

public class PriorityQueue<T extends Comparable<T>> implements Queue<T> {
    private Heap<T> heap;

    public PriorityQueue() {
        heap = new MaxHeap<>();
    }

    @Override
    public void enqueue(T value) {
        heap.add(value);
    }

    @Override
    public T dequeue() {
        return heap.extract();
    }

    @Override
    public T getFront() {
        return heap.findHeap();
    }

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

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

LeetCode算法题 https://leetcode-cn.com/problems/top-k-frequent-elements/

这是LeetCode的第347题——前K个高频元素

我们先用JDK的优先队列来完成,该优先队列使用的是平衡二叉最小堆来完成的。这里的所有类型皆为JDK自带类型,均为java.util包中。

class Solution {
    /**
     * 频次
     */
    private class Freq implements Comparable<Freq> {
        private int e;
        private int freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        public int getE() {
            return e;
        }

        public void setE(int e) {
            this.e = e;
        }

        public int getFreq() {
            return freq;
        }

        public void setFreq(int freq) {
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq o) {
            if (this.freq < o.freq) {
                return -1;
            }else if (this.freq > o.freq) {
                return 1;
            }else {
                return 0;
            }
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new TreeMap<>();
        for (int num : nums) {
            if (map.putIfAbsent(num,1) != null) {
                map.put(num,map.get(num) + 1);
            }
        }
        Queue<Freq> pq = new PriorityQueue<>();
        map.keySet().stream().forEach(key -> {
            if (pq.size() < k) {
                pq.add(new Freq(key,map.get(key)));
            }else if (map.get(key) > pq.peek().getFreq()) {
                pq.poll();
                pq.add(new Freq(key,map.get(key)));
            }
        });
        List<Integer> res = new LinkedList<>();
        while (!pq.isEmpty()) {
            res.add(pq.poll().getE());
        }
        return res;
    }
}

提交给LeetCode

  • 线段树封装

当我们在一个区间中进行统计和查询的时候,比如查询一个区间[i,j]的最大值,最小值,或者区间数字和,如果使用数组来遍历的话,它是一个O(n)的时间复杂度,但如果使用线段树,则时间复杂度就会减少到O(log n)级别。在线段树的应用中,区间本身是固定的,不考虑向区间中增加,删除元素的操作。

如果上图是一个求和的线段树,则根节点是整个区间A[0-7]所有元素的和,而下面的非叶节点分支则是不同中间分区间的元素的和。但并非所有的线段树都是一颗满二叉树。

由上图可以看到,线段树也不是一颗完全二叉树,但线段树是平衡二叉树。所谓平衡二叉树是指不同叶节点的深度最大不超过1。所以之前所说的堆也是平衡二叉树,但二分搜索树可能不是一颗平衡二叉树。虽然线段树不是完全二叉树,但依然可以用数组的形式来表示,我们可以将其看作是一颗满二叉树,只不过缺失的节点用空来表示。

如果区间有n个元素,用数组来组成线段树,根据满二叉树的原理,如果元素个数n刚好为2^k次幂个(如8个,16个),则组成线段树的数组空间需要2n,因为上层节点数之和约等于叶节点数(如叶节点是8的时候,上层节点数之和为7)。而元素个数不为2^k次幂时,就需要增加一排叶节点来组成满二叉树,而增加的这一排就会约等于上层满二叉树的节点数之和,上层满二叉树之和为2n,则组成线段树的数组空间需要4n。

接口

public interface SegmentTree<T> {
    T get(int index);
    int getSize();

    /**
     * 返回区间[queryL,queryR]的值
     * @param queryL
     * @param queryR
     * @return
     */
    T query(int queryL,int queryR);
    void set(int index,T t);
}

实现类

public class DefaultSegmentTree<T> implements SegmentTree<T> {
    /**
     * 区间元素
     */
    private T[] data;
    /**
     * 线段树
     */
    private T[] tree;
    /**
     * 函数式接口,继承于BiFunction,用做线段树规则(求和,求最大,最小等等)
     */
    private BinaryOperator<T> merger;

    @SuppressWarnings("unchecked")
    public DefaultSegmentTree(T[] data,BinaryOperator<T> merger) {
        this.merger = merger;
        this.data = (T[]) new Object[data.length];
        for (int i = 0;i < data.length;i++) {
            this.data[i] = data[i];
        }
        tree = (T[]) new Object[data.length * 4];
        buildSegmentTree(0,0,data.length - 1);
    }

    /**
     * 在treeIndex的位置创建表示区间[l...r]的线段树
     * @param treeIndex 根节点的索引
     * @param l 区间左边界
     * @param r 区间右边界
     */
    private void buildSegmentTree(int treeIndex,int l,int r) {
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChile(treeIndex);
        int mid = l + (r - l) / 2;
        buildSegmentTree(leftTreeIndex,l,mid);
        buildSegmentTree(rightTreeIndex,mid + 1,r);
        tree[treeIndex] = merger.apply(tree[leftTreeIndex],tree[rightTreeIndex]);
    }

    @Override
    public T get(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("索引非法");
        }
        return data[index];
    }

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

    @Override
    public T query(int queryL, int queryR) {
        if (queryL < 0 || queryL >= data.length
                || queryR < 0 || queryR >= data.length || queryL > queryR) {
            throw new IllegalArgumentException("索引非法");
        }
        return query(0,0,data.length - 1,queryL,queryR);
    }

    /**
     * 在以treeID为根的线段树中[l...r]的范围里,搜索区间[queryL...queryR]的值
     * @param treeIndex 根节点的索引
     * @param l 区间的左边界
     * @param r 区间的右边界
     * @param queryL 查询的左边界
     * @param queryR 查询的右边界
     * @return
     */
    private T query(int treeIndex,int l,int r,int queryL,int queryR) {
        if (l == queryL && r == queryR) {
            return tree[treeIndex];
        }
        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChile(treeIndex);
        if (queryL >= mid + 1) {
            return query(rightTreeIndex,mid + 1,r,queryL,queryR);
        }else if (queryR <= mid) {
            return query(leftTreeIndex,l,mid,queryL,queryR);
        }
        T leftResult = query(leftTreeIndex, l, mid, queryL, mid);
        T rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
        return merger.apply(leftResult,rightResult);
    }

    @Override
    public void set(int index, T value) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("索引非法");
        }
        data[index] = value;
        set(0,0,data.length - 1,index,value);
    }

    /**
     * 在以treeIndex为根的线段树中更新index的值为value
     * @param treeIndex
     * @param l
     * @param r
     * @param index
     * @param value
     */
    private void set(int treeIndex,int l,int r,int index,T value) {
        if (l == r) {
            tree[treeIndex] = value;
            return;
        }
        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChile(treeIndex);
        if (index >= mid + 1) {
            set(rightTreeIndex,mid + 1,r,index,value);
        }else {
            set(leftTreeIndex,l,mid,index,value);
        }
        tree[treeIndex] = merger.apply(tree[leftTreeIndex],tree[rightTreeIndex]);
    }

    /**
     * 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
     * @param index
     * @return
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
     * @param index
     * @return
     */
    private int rightChile(int index) {
        return index * 2 + 2;
    }

    @Override
    public String toString() {
        return "DefaultSegmentTree{" +
                "tree=" + Arrays.toString(tree) +
                '}';
    }
}

调用

public class SegmentTreeMain {
    public static void main(String[] args) {
        Integer[] nums = {-2,0,3,-5,2,-1};
        SegmentTree<Integer> segmentTree = new DefaultSegmentTree<>(nums,(x,y) -> x + y);
        System.out.println(segmentTree);
        System.out.println(segmentTree.query(0,2));
        segmentTree.set(3,5);
        System.out.println(segmentTree);
        System.out.println(segmentTree.query(1,4));
    }
}

运行结果

DefaultSegmentTree{tree=[-3, 1, -4, -2, 3, -3, -1, -2, 0, null, null, -5, 2, null, null, null, null, null, null, null, null, null, null, null]} 1 DefaultSegmentTree{tree=[7, 1, 6, -2, 3, 7, -1, -2, 0, null, null, 5, 2, null, null, null, null, null, null, null, null, null, null, null]} 10

从结果可以看到-3为所有元素的和。1为前3个元素的和,-4为后3个元素的和。而我们要查询的0到2区间的和为1。-5变更为5后,整个线段树重新变更结果。

LeetCode算法题 https://leetcode-cn.com/problems/range-sum-query-immutable/

这是LeetCode算法题的303题——区域和检索-数组不可变

这里我们就使用线段树来完成。

class NumArray {
    private SegmentTree<Integer> segmentTree;

    public NumArray(int[] nums) {
        if (nums.length > 0) {
            Integer[] data = new Integer[nums.length];
            for (int i = 0;i < nums.length;i++) {
                data[i] = nums[i];
            }
            segmentTree = new DefaultSegmentTree<>(data,(x, y) -> x + y);
        }
    }

    public int sumRange(int i, int j) {
        if (segmentTree == null) {
            throw new IllegalArgumentException("线段树为空");
        }
        return segmentTree.query(i,j);
    }
}

提交给LeetCode(提交的时候需要把线段树的接口以及实现类以私有方式放入NumArray类中)

不使用线段树,而采用预处理来完成

class NumArray {
    //预处理,sum[i]存储前i个元素和,sum[0] = 0
    //sum[i]存储nums[0...i-1]的和
    private int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        sum[0] = 0;
        for (int i = 1;i < sum.length;i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

提交给LeetCode

LeetCode算法题 https://leetcode-cn.com/problems/range-sum-query-mutable/

这是LeetCode的第307题——区域和检索-数组可修改

我们依然使用线段树来处理

class NumArray {
    private SegmentTree<Integer> segmentTree;

    public NumArray(int[] nums) {
        if (nums.length > 0) {
            Integer[] data = new Integer[nums.length];
            for (int i = 0;i < nums.length;i++) {
                data[i] = nums[i];
            }
            segmentTree = new DefaultSegmentTree<>(data,(x,y) -> x + y);
        }
    }

    public void update(int i, int val) {
        if (segmentTree == null) {
            throw new IllegalArgumentException("线段树为空");
        }
        segmentTree.set(i,val);
    }

    public int sumRange(int i, int j) {
        if (segmentTree == null) {
            throw new IllegalArgumentException("线段树为空");
        }
        return segmentTree.query(i,j);
    }
}

提交给LeetCode(提交的时候需要把线段树的接口以及实现类以私有方式放入NumArray类中)

  • 字典树封装

字典树是一种查询每一个条目的时间复杂度,和字典中一共有多少条目无关的数据结构。而其时间复杂度为O(w),w为查询单词的长度。字典树是一个多叉树,对于小写英文字母来说,可以有26个指向下个节点的指针。

接口

public interface Trie {
    int getSize();
    void add(String word);
    boolean contains(String word);
    boolean isEmpty();
    boolean isPrefix(String prefix);
    void remove(String word);
}

实现类(此处的Map和TreeMap皆为JDK内置)

public class DefaultTrie implements Trie {
    @Data
    private class Node {
        //单词节点的末尾
        private Boolean word;
        private Map<Character,Node> next;

        public Node(boolean word) {
            this.word = word;
            next = new TreeMap<>();
        }

        public Node() {
            this(false);
        }
    }

    private Node root;
    private int size;

    public DefaultTrie() {
        root = new Node();
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public void add(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            cur.getNext().putIfAbsent(c,new Node());
            cur = cur.getNext().get(c);
        }
        if (!cur.getWord()) {
            cur.setWord(true);
            size++;
        }
    }

    @Override
    public boolean contains(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            if (cur.getNext().get(c) == null) {
                return false;
            }
            cur = cur.getNext().get(c);
        }
        return cur.getWord();
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isPrefix(String prefix) {
        Node cur = root;
        for (int i = 0;i < prefix.length();i++) {
            char c = prefix.charAt(i);
            if (cur.getNext().get(c) == null) {
                return false;
            }
            cur = cur.getNext().get(c);
        }
        return true;
    }

    @Override
    public void remove(String word) {
        if (contains(word)) {
            remove(word,word.length() - 1);
         }
    }

    private void remove(String word,int index) {
        if (index + 1 == word.length()) {
            Node node = get(word,index);
            char c = word.charAt(index);
            if (node.getNext().size() == 1 && mapIsEmpty(node.getNext().get(c).getNext())) {
                node.setNext(null);
            }else if (node.getNext().size() == 1 && node.getNext().get(c).getWord()) {
                node.getNext().get(c).setWord(false);
                size--;
                return;
            }else {
                node.getNext().remove(c);
                size--;
                return;
            }
            word = word.substring(0,word.length() - 1);
        }
        remove(word,index - 1);
    }

    private Node get(String word,int index) {
        Node cur = root;
        for (int i = 0;i < index;i++) {
            char c = word.charAt(i);
            cur = cur.getNext().get(c);
        }
        return cur;
    }

    private boolean mapIsEmpty(Map<?, ?> map) {
        return map == null || map.isEmpty();
    }

    @Override
    public String toString() {
        return "DefaultTrie{" +
                "root=" + root +
                ", size=" + size +
                '}';
    }
}

调用

public class TrieMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Trie trie = new DefaultTrie();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(trie::add);
        System.out.println("共有不同的单词: " + trie.getSize());
    }
}

运行结果

傲慢与偏见 共有单词: 125901 共有不同的单词: 6530

删除测试

public class TrieRemoveMain {
    public static void main(String[] args) {
        Trie trie = new DefaultTrie();
        trie.add("adfatr");
        trie.add("adfadhy");;
        trie.add("adfasd");
        trie.remove("adfadhy");
        System.out.println(trie);
    }
}

运行结果

DefaultTrie{root=DefaultTrie.Node(word=false, next={a=DefaultTrie.Node(word=false, next={d=DefaultTrie.Node(word=false, next={f=DefaultTrie.Node(word=false, next={a=DefaultTrie.Node(word=false, next={s=DefaultTrie.Node(word=false, next={d=DefaultTrie.Node(word=true, next={})}), t=DefaultTrie.Node(word=false, next={r=DefaultTrie.Node(word=true, next={})})})})})})}), size=2}

由于字典树的设计有可能占用空间过大,所以有一种设计为压缩字典树

关于压缩字典树的应用可以参考字典树收集(初步读写锁实现线程安全,待续)

LeetCode算法题 https://leetcode-cn.com/problems/implement-trie-prefix-tree/

这是LeetCode的208题——实现Trie(前缀树)

该题跟我们实现的字典树完全一样,只是方法名称不同。

class Trie {
    private class Node {
        //单词节点的末尾
        private Boolean word;
        private Map<Character,Node> next;

        public Node(boolean word) {
            this.word = word;
            next = new TreeMap<>();
        }

        public Node() {
            this(false);
        }

        public Boolean getWord() {
            return word;
        }

        public void setWord(Boolean word) {
            this.word = word;
        }

        public Map<Character, Node> getNext() {
            return next;
        }

        public void setNext(Map<Character, Node> next) {
            this.next = next;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            cur.getNext().putIfAbsent(c,new Node());
            cur = cur.getNext().get(c);
        }
        if (!cur.getWord()) {
            cur.setWord(true);
        }
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            if (cur.getNext().get(c) == null) {
                return false;
            }
            cur = cur.getNext().get(c);
        }
        return cur.getWord();
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Node cur = root;
        for (int i = 0;i < prefix.length();i++) {
            char c = prefix.charAt(i);
            if (cur.getNext().get(c) == null) {
                return false;
            }
            cur = cur.getNext().get(c);
        }
        return true;
    }
}

提交给LeetCode

LeetCode算法题 https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/

这是LeetCode的第211题——添加与搜索单词-数据结构设计

这道题的重点依然是递归的使用

class WordDictionary {
    private class Node {
        //单词节点的末尾
        private Boolean word;
        private Map<Character,Node> next;

        public Node(boolean word) {
            this.word = word;
            next = new TreeMap<>();
        }

        public Node() {
            this(false);
        }

        public Boolean getWord() {
            return word;
        }

        public void setWord(Boolean word) {
            this.word = word;
        }

        public Map<Character, Node> getNext() {
            return next;
        }

        public void setNext(Map<Character, Node> next) {
            this.next = next;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            cur.getNext().putIfAbsent(c,new Node());
            cur = cur.getNext().get(c);
        }
        if (!cur.getWord()) {
            cur.setWord(true);
        }
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return match(root,word,0);
    }

    private boolean match(Node node,String word,int index) {
        if (index == word.length()) {
            return node.getWord();
        }
        char c = word.charAt(index);
        if (c != '.') {
            if (node.getNext().get(c) == null) {
                return false;
            }
            return match(node.getNext().get(c),word,index + 1);
        }else {
            //遍历所有的字符节点,进行递归
            for (char nextChar : node.getNext().keySet()) {
                if (match(node.getNext().get(nextChar),word,index + 1)) {
                    return true;
                }
            }
            return false;
        }
    }
}

提交给LeetCode

LeetCode算法题 https://leetcode-cn.com/problems/map-sum-pairs/

这是LeetCode的第677题——键值映射

同样也是使用递归来获取

class MapSum {
    private class Node {
        private int value;
        private Map<Character,Node> next;

        public Node(int value) {
            this.value = value;
            next = new TreeMap<>();
        }

        public Node() {
            this(0);
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Map<Character, Node> getNext() {
            return next;
        }

        public void setNext(Map<Character, Node> next) {
            this.next = next;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public MapSum() {
        root = new Node();
    }

    public void insert(String key, int val) {
        Node cur = root;
        for (int i = 0;i < key.length();i++) {
            char c = key.charAt(i);
            cur.getNext().putIfAbsent(c,new Node());
            cur = cur.getNext().get(c);
        }
        cur.setValue(val);
    }

    public int sum(String prefix) {
        Node cur = root;
        for (int i = 0;i < prefix.length();i++) {
            char c = prefix.charAt(i);
            if (cur.getNext().get(c) == null) {
                return 0;
            }
            cur = cur.getNext().get(c);
        }
        return sum(cur);
    }

    private int sum(Node node) {
        int ret = node.getValue();
        for (char c : node.getNext().keySet()) {
            ret += sum(node.getNext().get(c));
        }
        return ret;
    }
}

提交给LeetCode

  • 并查集封装

并查集是解决连接问题的一种数据结构。我们认为在同一个集合中,两个元素是必然连接的,而不同的集合是不连接的。在并查集中,类似于线段树,同样不考虑并查集的增加、删除元素的操作。

接口

public interface UnionFind {
    int getSize();

    /**
     * 查看元素p和元素q是否所属同一个集合
     * @param p
     * @param q
     * @return
     */
    boolean isConnected(int p,int q);

    /**
     * 合并元素p和元素q所属的集合
     * @param p
     * @param q
     */
    void unionElements(int p,int q);
}

数组实现类

public class ArrayUnionFind implements UnionFind {
    //该数组的索引,我们称为元素的编号
    //该数组的值,我们称之为元素所属不同集合的编号
    //如果不同索引的值相同,则表示不同的元素属于同一个集合
    private int[] id;

    public ArrayUnionFind(int size) {
        id = new int[size];
        for (int i = 0;i < id.length;i++) {
            id[i] = i;
        }
    }

    /**
     * 查找元素p所对应的集合编号
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= id.length) {
            throw new IllegalArgumentException("p越界");
        }
        return id[p];
    }

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID) {
            return;
        }
        for (int i = 0;i < id.length;i++) {
            if (id[i] == pID) {
                id[i] = qID;
            }
        }
    }
}

对于ArrayUnionFind各操作的时间复杂度

isConnected(p,q) O(1)

unionElements(p,q) O(n)

由于ArrayUnionFind的unionElements()方法是O(n)级别的,所以在数据量比较大的情况下,它是无法支撑的。但因为它的isConnected()方法是O(1)级别的,所以我们称该实现类为Quick Find,而我们要改进的是Quick Union。

树实现类

我们将数组中的每个元素都当成一颗独立的树,初始化时,它们都是自己指向自己的指针。意思就是说每个元素的集合编号就是它们自己。

如果此时我们要改变元素4的集合编号变更为3的时候

此时我们又要将3的元素的集合编号变更为8

元素6的集合编号变更为5

元素9的集合编号变更与4相同,由于4的属于集合编号3的,而元素3是属于集合编号8的,所以要让9与4有相同的集合编号,所以9需要指向4的根节点的集合编号8.

元素2的集合编号变更为1

元素5的集合编号变更为0

元素7的集合编号变更与2相同,所以7的集合编号变更为2的根节点1

元素6的集合编号变更与2相同,只需要变更6的根结点0的集合编号为2的根节点的集合编号1

public class TreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时,表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时,表示向上指针指向其他元素
    private int[] parent;

    public TreeUnionFind(int size) {
        parent = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
        }
    }

    /**
     * 不断向上查找元素的根节点,直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        parent[pRoot] = qRoot;
    }
}

对于TreeUnionFind各操作的时间复杂度

isConnected(p,q) O(h) h为树的高度

unionElements(p,q) O(h) h为树的高度

两种并查集的性能测试

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 1000000;
        int m = 10000;
        UnionFind arrayUnionFind = new ArrayUnionFind(size);
        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind treeUnionFind = new TreeUnionFind(size);
        System.out.println("treeUnionFind : " + testUF(treeUnionFind,m) + " s");
    }
}

测试结果

arrayUnionFind : 2.232692422 s treeUnionFind : 0.002538113 s

但是当我们调整m的合并集合次数的时候

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 100000;
        int m = 100000;
        UnionFind arrayUnionFind = new ArrayUnionFind(size);
        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind treeUnionFind = new TreeUnionFind(size);
        System.out.println("treeUnionFind : " + testUF(treeUnionFind,m) + " s");
    }
}

测试结果

arrayUnionFind : 4.139503265 s treeUnionFind : 8.657331935 s

出现这种情况,是因为在数组并查集,虽然它的合并集合unionElements()方法是O(n)级别的,但由于数组的内存地址是连续的,而树并查级的内存地址是非连续的,这里需要有一定的时间延迟,连续地址比非连续地址要快。而更重要的是增大了合并的次数m,有可能产生了类似于链表的树结构,也就是说树的高度接近于链表的长度,所以O(h)接近于O(n)。针对这个问题,我们需要改进合并集合的方式,让树向多分叉方向变化,而不是向链表方向变化。

改进的树并查集实现类,我们称之为基于树的节点元素个数的优化——size优化

public class SizeTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时,表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时,表示向上指针指向其他元素
    private int[] parent;
    //sz[i]表示以i为根的集合中元素个数
    private int[] sz;

    public SizeTreeUnionFind(int size) {
        parent = new int[size];
        sz = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点,直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的元素个数不同判断合并方向
        //将元素个数少的集合合并到元素个数多的集合上,降低树的高度
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}

重新测试

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 100000;
        int m = 100000;
        UnionFind arrayUnionFind = new ArrayUnionFind(size);
        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind sizeTreeUnionFind = new SizeTreeUnionFind(size);
        System.out.println("sizeTreeUnionFind : " + testUF(sizeTreeUnionFind,m) + " s");
    }
}

测试结果

arrayUnionFind : 4.08657561 s sizeTreeUnionFind : 0.019326149 s

基于降低树的高度的思想,我们又可以重新修改树并查集的代码,专门基于树的高度来进行优化

假设有现在的这种情况

此时我们要将4的元素的集合编号变更为与2相同,根据size的优化思路,由于2所在集合的元素要多于4所在集合的元素,所以我们此时合并集合后的结果如下,4的根节点8指向2的根节点7.

但是这样合并集合,无疑增大了树的高度,所以我们要让原树的高度低的合并到原树的高度高的中去,合并后结果如下

层级并查树实现类

public class RankTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时,表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时,表示向上指针指向其他元素
    private int[] parent;
    //rank[i]表示以i为根的集合所表示的树的层数
    private int[] rank;

    public RankTreeUnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点,直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        }else {
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }
}

现在我们调大合并集合的次数,重新测试,由于数组并查集合并集合方法为O(n)级别,所以不参与,无法完成运算

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 10000000;
        int m = 10000000;
//        UnionFind arrayUnionFind = new ArrayUnionFind(size);
//        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind sizeTreeUnionFind = new SizeTreeUnionFind(size);
        System.out.println("sizeTreeUnionFind : " + testUF(sizeTreeUnionFind,m) + " s");

        UnionFind rankTreeUnionFind = new RankTreeUnionFind(size);
        System.out.println("rankTreeUnionFind : " + testUF(rankTreeUnionFind,m) + " s");
    }
}

测试结果

sizeTreeUnionFind : 5.12385286 s rankTreeUnionFind : 4.823445856 s

路径压缩 现在我们都知道了,在并查集中,类似于下面这种树的集合其实是一个意思,它们都表示0、1、2、3、4这个5个元素属于同一个集合,集合编号为0,它们的根节点都是0。但由于这三种树的深度不同,所以查询根节点的效率是不同的。

而路径压缩要解决的问题就是将一颗比较高的树压缩成一颗比较矮的树。当我们在查找一个节点的根节点find()的过程中,顺便进行一下路径压缩。比如我们在最左边的图(类似链表)中查找4的根结点的时候,将4的父节点变更为其父节点的父节点,即parent[4] = parent[parent[4]],这样图形就发生了如下的变化

由于2并非根节点,继续向上遍历,同时将2的父节点变更为2的父节点的父节点parent[2] = parent[parent[2]],这样图形就发生了如下变化。

由于找到了根节点0,此时查找根节点find()结束。而整颗树的高度也变得更矮。所以SizeTreeUnionFind和RankTreeUnionFind也相应变更为

public class SizeTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时,表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时,表示向上指针指向其他元素
    private int[] parent;
    //sz[i]表示以i为根的集合中元素个数
    private int[] sz;

    public SizeTreeUnionFind(int size) {
        parent = new int[size];
        sz = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点,直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的元素个数不同判断合并方向
        //将元素个数少的集合合并到元素个数多的集合上,降低树的高度
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}
public class RankTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时,表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时,表示向上指针指向其他元素
    private int[] parent;
    //rank[i]表示以i为根的集合所表示的树的层数
    private int[] rank;

    public RankTreeUnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点,直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        }else {
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }
}

重新测试TestUnionFindMain,结果如下

sizeTreeUnionFind : 3.952670823 s rankTreeUnionFind : 3.968889342 s

当然我们也可以直接借助递归将一颗树的高度变成2

递归层级并查集实现类

public class RecursiveRankTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时,表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时,表示向上指针指向其他元素
    private int[] parent;
    //rank[i]表示以i为根的集合所表示的树的层数
    private int[] rank;

    public RecursiveRankTreeUnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点,直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        if (p != parent[p]) {
            parent[p] = find(parent[p]);
        }
        return parent[p];
    }

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        }else {
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }
}

测试

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 10000000;
        int m = 10000000;
//        UnionFind arrayUnionFind = new ArrayUnionFind(size);
//        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind sizeTreeUnionFind = new SizeTreeUnionFind(size);
        System.out.println("sizeTreeUnionFind : " + testUF(sizeTreeUnionFind,m) + " s");

        UnionFind rankTreeUnionFind = new RankTreeUnionFind(size);
        System.out.println("rankTreeUnionFind : " + testUF(rankTreeUnionFind,m) + " s");

        UnionFind recursiveRankTreeUnionFind = new RecursiveRankTreeUnionFind(size);
        System.out.println("recursiveRankTreeUnionFind : " + testUF(recursiveRankTreeUnionFind,m) + " s");
    }
}

测试结果

sizeTreeUnionFind : 3.891047143 s rankTreeUnionFind : 3.949480955 s recursiveRankTreeUnionFind : 4.489701369 s

由结果可知,递归层级并查集的速度要慢过非递归,原因在于非递归的方式也可以最终将一棵树的高度降低为2,只不过不是一次调用,而是多次调用。而递归的方式本身会增加复杂度,增大开销。如下图所示,如果我们再次调用find(4)的时候,4的父节点就指向了父节点2的父节点0.

如果再调用一次find(3),则将最终演变成一颗高度为2的树

  • AVL树封装

AVL树是一种保持平衡的二分搜索树,使得该二分搜索树不会退化为一个链表。

平衡二叉树——对于任意一个节点,左子树和右子树的高度差不能超过1。平衡二叉树的高度和节点数量之间的关系也是O(log n)的。

由此可以定义任意一个节点的高度为左右子树较高的那颗子树的高度+1,加的这个1就是节点本身。

以上图数字5为例,他的左右子树的高度,分别为2和1,则5节点的高度为左右子树中高的子树的高度加1,则其高度为3.

我们定义一个节点的平衡因子为该节点左右子树的高度差,则很明显,当平衡因子为大于0的时候,说明左子树高于右子树;当平衡因子小于0的时候,说明右子树高于左子树。而当平衡因子大于1或者小于-1的时候,我们知道,该节点失去了平衡性。

又根据平衡二叉树的定义,我们知道上面这颗二分搜索树并不是一个平衡二分搜索树,因为到8这个节点的时候,它的平衡因子为2,超过了1.所以我们在AVL树的实现的时候,需要保持8这个节点的平衡性。

要维护一个节点的平衡性需要考虑4种情况

1、一直向一颗树的左侧添加元素,我们可以用LL来标记

此时可以肯定的是该节点的平衡因子是大于1的(左子树高过右子树2,一般也就高过2,不会超过2),且该节点的左节点的平衡因子大于等于0才可能是一直向左侧添加元素.

右旋转

假设我们现在在树的最左侧添加了一个节点,并打破了平衡性,y的平衡因子为2.根据二分搜索树的性质(节点左子树的元素一律小于该节点的元素,节点右子树的元素,一律大于该节点元素),此时图中各个元素的大小排序为

T1 < z < T2 < x < T3 < y < T4

当我们转换图形的位置如下时

各个元素的大小排序为

T1 < z < T2 < x < T3 < y < T4,可见元素的顺序并没有发生改变,说明这样的一颗二分搜索树跟之前的是等价的。

而所要做出的调整就为将x的右节点变成y,x的原右节点T3变为y的左节点,我们将此过程称为右旋转。旋转完之后,我们需要维护x跟y的高度。

2、一直向一棵树的右侧一直添加元素,我们可以用RR来标记

此时可以肯定的是该节点的平衡因子是小于-1的(右子树高过左子树2),且该节点的右节点的平衡因子小于等于0才可能是一直向右侧添加元素.

左旋转

假设我们现在在树的最右侧添加了一个节点,并打破了平衡性,y的平衡因子为-2.根据二分搜索树的性质(节点左子树的元素一律小于该节点的元素,节点右子树的元素,一律大于该节点元素),此时图中各个元素的大小排序为

T4 < y < T3 < x < T1 < z < T2

当我们转换图形的位置如下时

各个元素的大小排序为

T4 < y < T3 < x < T1 < z < T2,可见元素的顺序并没有发生改变,说明这样的一颗二分搜索树跟之前的是等价的。

而所要做出的调整就为将x的左节点变成y,x的原左节点T3变为y的右节点,我们将此过程称为左旋转。旋转完之后,我们需要维护x跟y的高度。

3、向节点的左节点添加右节点,我们可以用LR标识

此时可以肯定的是该节点的平衡因子是大于1的(左子树高过右子树2),且该节点的左节点的平衡因子小于0才可能是这种情况。

现在我们知道无论对一颗二分搜索树做左旋转还是右旋转都不会改变一个二分搜索树的排序的性质,那么我们对x做一次左旋转,将x变成z的左节点,T2变成x的右节点。当然z要变成y的左节点。

那么此时,就变成了LL的情况,按照LL来处理就好了。

4、向节点的右节点添加左节点,我们可以用RL标识

此时可以肯定的是该节点的平衡因子是小于-1的(右子树高过左子树2),且该节点的右节点的平衡因子大于0才可能是这种情况。

此时我们只需要将x做一次右旋转,将x变成z的右节点,将T3变成x的左节点,当然z变成y的右节点。

那么此时,就变成了RR的情况,按照RR来处理就好了。

实现类

public class AVLTree<T extends Comparable<T>> implements Tree<T> {
    @Data
    @AllArgsConstructor
    private class Node{
        private T element;
        private Node left;
        private Node right;
        //节点的高度,在节点的左右子树增加、删除节点时需要维护该节点的高度
        private int height;

        public Node(T element) {
            this(element,null,null,1);
        }
    }

    private Node root;
    private int size;

    public AVLTree() {
        root = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.getHeight();
    }

    /**
     * 获得节点node的平衡因子(左右子树的高度差)
     * @param node
     * @return
     */
    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.getLeft()) - getHeight(node.getRight());
    }

    /**
     * 判断该二叉树是否是一颗二分搜索树
     * @return
     */
    public boolean isBST() {
        Array<T> elements = new DefaultArray<>();
        inOrder(root,elements);
        for (int i = 1;i < elements.getSize();i++) {
            if (elements.get(i - 1).compareTo(elements.get(i)) > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断该二叉树是否是一颗平衡二叉树
     * @return
     */
    public boolean isBalanced() {
        return isBalanced(root);
    }

    private boolean isBalanced(Node node) {
        if (node == null) {
            return true;
        }
        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {
            return false;
        }
        return isBalanced(node.getLeft()) && isBalanced(node.getRight());
    }

    /**
     * 对节点node进行右旋转操作,返回旋转后新的根节点(原node的左节点)
     * @param node
     * @return
     */
    private Node rightRotate(Node node) {
        Node ret = node.getLeft();
        Node rightRet = ret.getRight();
        //向右旋转的过程
        ret.setRight(node);
        node.setLeft(rightRet);
        //更新height
        node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1);
        ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1);

        return ret;
    }

    /**
     * 对节点node进行左旋转操作,返回旋转后新的根节点(原node的右节点)
     * @param node
     * @return
     */
    private Node leftRotate(Node node) {
        Node ret = node.getRight();
        Node leftRet = ret.getLeft();
        //向左旋转的过程
        ret.setLeft(node);
        node.setRight(leftRet);
        //更新height
        node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1);
        ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1);

        return ret;
    }

    @Override
    public void add(T value) {
        root = add(root,value);
    }

    private Node add(Node node,T value) {
        //递归终止条件
        if (node == null) {
            size++;
            return new Node(value);
        }
        //递归
        if (value.compareTo(node.getElement()) < 0) {
            node.setLeft(add(node.getLeft(),value));
        }else if (value.compareTo(node.getElement()) > 0) {
            node.setRight(add(node.getRight(),value));
        }
        return service(node);
    }

    @Override
    public boolean contains(T value) {
        return contains(root,value);
    }

    private boolean contains(Node node,T value) {
        if (node == null) {
            return false;
        }
        if (value.compareTo(node.getElement()) == 0) {
            return true;
        }else if (value.compareTo(node.getElement()) < 0) {
            return contains(node.getLeft(),value);
        }else {
            return contains(node.getRight(),value);
        }
    }

    @Override
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }

        System.out.println(node.getElement());
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }

    /**
     * 非递归前序遍历
     */
    public void preOrderNR() {
        Stack<Node> stack = new ArrayStack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.getElement());
            if (cur.getRight() != null) {
                stack.push(cur.getRight());
            }
            if (cur.getLeft() != null) {
                stack.push(cur.getLeft());
            }
        }
    }

    @Override
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.getLeft());
        System.out.println(node.getElement());
        inOrder(node.getRight());
    }

    private void inOrder(Node node,Array<T> elements) {
        if (node == null) {
            return;
        }
        inOrder(node.getLeft(),elements);
        elements.addLast(node.getElement());
        inOrder(node.getRight(),elements);
    }

    @Override
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.getLeft());
        postOrder(node.getRight());
        System.out.println(node.getElement());
    }

    @Override
    public void levelOrder() {
        Queue<Node> queue = new LoopQueue<>();
        queue.enqueue(root);
        while (!queue.isEmpty()) {
            Node cur = queue.dequeue();
            System.out.println(cur.getElement());

            if (cur.getLeft() != null) {
                queue.enqueue(cur.getLeft());
            }
            if (cur.getRight() != null) {
                queue.enqueue(cur.getRight());
            }
        }
    }

    @Override
    public T minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        return minimum(root).getElement();
    }

    private Node minimum(Node node) {
        if (node.getLeft() == null) {
            return node;
        }
        return minimum(node.getLeft());
    }

    @Override
    public T maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        return maximum(root).getElement();
    }

    private Node maximum(Node node) {
        if (node.getRight() == null) {
            return node;
        }
        return maximum(node.getRight());
    }

    @Override
    public T removeMin() {
        T ret = minimum();
        root = removeMin(root);
        return ret;
    }

    private Node removeMin(Node node) {
        //递归的终止条件,当节点的左子树为空时,递归达到最大深度
        if (node.getLeft() == null) {
            //保存最终节点的右子树
            Node rightNode = node.getRight();
            //将最终节点分离
            node.setRight(null);
            size--;
            //将保存的右子树拼接回最终节点的父节点
            return rightNode;
        }
        //从根节点开始不断向左子树递归,并逐层返回删除后的子节点重新
        //设为上层节点的左节点
        node.setLeft(removeMin(node.getLeft()));
        return service(node);
    }

    @Override
    public T removeMax() {
        T ret = maximum();
        root = removeMax(root);
        return ret;
    }

    private Node removeMax(Node node) {
        if (node.getRight() == null) {
            Node leftNode = node.getLeft();
            node.setLeft(null);
            size--;
            return leftNode;
        }

        node.setRight(removeMax(node.getRight()));
        return service(node);
    }

    @Override
    public void remove(T value) {
        root = remove(root,value);
    }

    private Node remove(Node node,T value) {
        if (node == null) {
            return null;
        }
        Node retNode;
        if (value.compareTo(node.getElement()) < 0) {
            node.setLeft(remove(node.getLeft(),value));
            retNode = node;
        }else if (value.compareTo(node.getElement()) > 0) {
            node.setRight(remove(node.getRight(),value));
            retNode = node;
        }else {
            //待删除节点左子树为空的情况
            if (node.getLeft() == null) {
                Node rightNode = node.getRight();
                node.setRight(null);
                size--;
                retNode = rightNode;
            }
            //待删除节点右子树为空的情况
            else if (node.getRight() == null) {
                Node leftNode = node.getLeft();
                node.setLeft(null);
                size--;
                retNode = leftNode;
            }else {
                //待删除节点左右子树均不为空的情况
                //找到比待删除节点大的最小节点,即待删除节点右子树的最小节点
                //用这个节点顶替待删除节点的位置
                Node successor = minimum(node.getRight());
                successor.setRight(removeMin(node.getRight()));
                successor.setLeft(node.getLeft());
                node.setLeft(null);
                node.setRight(null);
                retNode = successor;
                //找到比待删除节点小的最大节点,即待删除节点左子树的最大节点
                //用这个节点顶替待删除节点的位置,此二种方法取其一即可
//            Node predecessor = maximum(node.getLeft());
//            predecessor.setLeft(removeMax(node.getLeft()));
//            predecessor.setRight(node.getRight());
//            node.setLeft(null);
//            node.setRight(null);
//            return predecessor;
            }
        }
        if (retNode == null) {
            return null;
        }
        return service(retNode);
    }

    /**
     * 维护节点平衡
     * @param node
     * @return
     */
    private Node service(Node node) {
        //更新height
        node.setHeight(1 + Math.max(getHeight(node.getLeft()),getHeight(node.getRight())));
        //计算平衡因子
        int balanceFactor = getBalanceFactor(node);

        //平衡维护
        //LL
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) >= 0) {
            return rightRotate(node);
        }
        //RR
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) <= 0) {
            return leftRotate(node);
        }
        //LR
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) < 0) {
            node.setLeft(leftRotate(node.getLeft()));
            return rightRotate(node);
        }
        //RL
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) > 0) {
            node.setRight(rightRotate(node.getRight()));
            return leftRotate(node);
        }
        return node;
    }

    @Override
    public T floor(T value) {
        Node node = floor(root,value);
        if (node != null) {
            return node.getElement();
        }
        return null;
    }

    private Node floor(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) <= 0) {
            return floor(node.getLeft(),value);
        }else {
            if (node.getRight() == null) {
                return node;
            }else if (node.getRight().getLeft() == null &&
                    value.compareTo(node.getRight().getElement()) <= 0) {
                return node;
            }else if (node.getRight().getRight() == null &&
                    value.compareTo(node.getRight().getElement()) > 0) {
                return node.getRight();
            }
            return floor(node.getRight(),value);
        }
    }

    @Override
    public T ceil(T value) {
        Node node = ceil(root,value);
        if (node != null) {
            return node.getElement();
        }
        return null;
    }

    private Node ceil(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) >= 0) {
            return ceil(node.getRight(),value);
        }else {
            if (node.getLeft() == null) {
                return node;
            }else if (value.compareTo(maximum(node.getLeft()).getElement()) >= 0) {
                return node;
            }else if (node.getLeft().getRight() == null &&
                    value.compareTo(node.getLeft().getElement()) >= 0) {
                return node;
            }else if (node.getLeft().getLeft() == null &&
                    value.compareTo(node.getLeft().getElement()) < 0) {
                return node.getLeft();
            }
            return ceil(node.getLeft(),value);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        generateBSTString(root,0,builder);
        return builder.toString();
    }

    private void generateBSTString(Node node,int depth,StringBuilder builder) {
        if (node == null) {
            builder.append(generateDepthString(depth) + "null\n");
            return;
        }
        builder.append(generateDepthString(depth) + node.getElement() + "\n");
        generateBSTString(node.getLeft(),depth + 1,builder);
        generateBSTString(node.getRight(),depth + 1,builder);
    }

    private String generateDepthString(int depth) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i < depth;i++) {
            builder.append("--");
        }
        return builder.toString();
    }
}
  • AVL树映射封装

实现类

public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V> {
    @Data
    @AllArgsConstructor
    private class Node{
        private K key;
        private V value;
        private Node left;
        private Node right;
        private int height;

        public Node(K key) {
            this(key,null,null,null,1);
        }
        public Node(K key,V value) {
            this(key,value,null,null,1);
        }
    }

    private Node root;
    private int size;

    public AVLTreeMap() {
        root = null;
        size = 0;
    }

    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.getHeight();
    }

    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.getLeft()) - getHeight(node.getRight());
    }

    private Node rightRotate(Node node) {
        Node ret = node.getLeft();
        Node retRight = ret.getRight();
        ret.setRight(node);
        node.setLeft(retRight);
        node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1);
        ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1);
        return ret;
    }

    private Node leftRotate(Node node) {
        Node ret = node.getRight();
        Node retLeft = ret.getLeft();
        ret.setLeft(node);
        node.setRight(retLeft);
        node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1);
        ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1);
        return ret;
    }

    @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.getKey()) < 0) {
            node.setLeft(add(node.getLeft(),key,value));
        }else if (key.compareTo(node.getKey()) > 0) {
            node.setRight(add(node.getRight(),key,value));
        }else {
            node.setValue(value);
        }
        return service(node);
    }

    @Override
    public V remove(K key) {
        Node node = getNode(root,key);
        if (node != null) {
            root = remove(root,key);
            return node.getValue();
        }
        return null;
    }

    private Node remove(Node node, K key) {
        if (node == null) {
            return null;
        }
        Node retNode;
        if (key.compareTo(node.getKey()) < 0) {
            node.setLeft(remove(node.getLeft(),key));
            retNode = node;
        }else if (key.compareTo(node.getKey()) > 0) {
            node.setRight(remove(node.getRight(),key));
            retNode = node;
        }else {
            //待删除节点左子树为空的情况
            if (node.getLeft() == null) {
                Node rightNode = node.getRight();
                node.setRight(null);
                size--;
                retNode = rightNode;
            }
            //待删除节点右子树为空的情况
            else if (node.getRight() == null) {
                Node leftNode = node.getLeft();
                node.setLeft(null);
                size--;
                retNode = leftNode;
            }else {
                //待删除节点左右子树均不为空的情况
                //找到比待删除节点大的最小节点,即待删除节点右子树的最小节点
                //用这个节点顶替待删除节点的位置
                Node successor = minimum(node.getRight());
                successor.setRight(removeMin(node.getRight()));
                successor.setLeft(node.getLeft());
                node.setLeft(null);
                node.setRight(null);
                retNode = successor;
            }
        }
        if (retNode == null) {
            return null;
        }
        return service(retNode);
    }

    private Node service(Node node) {
        node.setHeight(1 + Math.max(getHeight(node.getLeft()),getHeight(node.getRight())));
        int balanceFactor = getBalanceFactor(node);
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) >= 0) {
            return rightRotate(node);
        }
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) <= 0) {
            return leftRotate(node);
        }
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) < 0) {
            node.setLeft(leftRotate(node.getLeft()));
            return rightRotate(node);
        }
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) > 0) {
            node.setRight(rightRotate(node.getRight()));
            return leftRotate(node);
        }
        return node;
    }

    private Node minimum(Node node) {
        if (node.getLeft() == null) {
            return node;
        }
        return minimum(node.getLeft());
    }

    private Node removeMin(Node node) {
        if (node.getLeft() == null) {
            Node rightNode = node.getRight();
            node.setRight(null);
            size--;
            return rightNode;
        }
        node.setLeft(removeMin(node.getLeft()));
        return service(node);
    }

    @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.getValue();
    }

    @Override
    public void set(K key, V value) {
        Node node = getNode(root,key);
        if (node == null) {
            throw new IllegalArgumentException(key + "不存在");
        }
        node.setValue(value);
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private Node getNode(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.getKey()) == 0) {
            return node;
        }else if (key.compareTo(node.getKey()) < 0) {
            return getNode(node.getLeft(),key);
        }else {
            return getNode(node.getRight(),key);
        }
    }
}

调用

public class MapMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Map<String,Integer> map = new AVLTreeMap<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
    }
}

运行结果

傲慢与偏见 共有单词: 125901 共有不同的单词: 6530 pride出现的次数: 53 prejudice出现的次数: 11

三种映射的性能测试

public class TestMapMain {
    private static double testMap(Map<String,Integer> map,String filename) {
        long startTime = System.nanoTime();
        System.out.println(filename);
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile(filename,words);
        System.out.println("共有单词: " + words.getSize());
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        String filename = "/Users/admin/Downloads/pride-and-prejudice.txt";
        Map<String,Integer> bstMap = new BSTMap<>();
        double time1 = testMap(bstMap,filename);
        System.out.println("BST Map: " + time1 + " s");

        Map<String,Integer> linkedListMap = new LinkedListMap<>();
        double time2 = testMap(linkedListMap,filename);
        System.out.println("LinkedList Map: " + time2 + " s");

        Map<String,Integer> avlTreeMap = new AVLTreeMap<>();
        double time3 = testMap(avlTreeMap,filename);
        System.out.println("AVLTree Map: " + time3 + " s");
    }
}

测试结果

/Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同的单词: 6530 pride出现的次数: 53 prejudice出现的次数: 11 BST Map: 0.166421303 s /Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同的单词: 6530 pride出现的次数: 53 prejudice出现的次数: 11 LinkedList Map: 9.416305469 s /Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同的单词: 6530 pride出现的次数: 53 prejudice出现的次数: 11 AVLTree Map: 0.065798621 s

  • AVL树集合封装

实现类

public class AVLTreeSet<T extends Comparable<T>> implements Set<T> {
    private Tree<T> avlTree;

    public AVLTreeSet() {
        avlTree = new AVLTree<>();
    }

    @Override
    public void add(T value) {
        avlTree.add(value);
    }

    @Override
    public void remove(T value) {
        avlTree.remove(value);
    }

    @Override
    public boolean contains(T value) {
        return avlTree.contains(value);
    }

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

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

三种集合的性能测试

public class TestSetMain {
    private static double testSet(Set<String> set,String filename) {
        long startTime = System.nanoTime();
        System.out.println(filename);
        Array<String> words = new DefaultArray<>();
        if (FileOperation.readFile(filename,words)) {
            System.out.println("共有单词: " + words.getSize());
            Stream.of(words.getData()).filter(data -> data != null)
                    .forEach(set::add);
            System.out.println("共有不同单词: " + set.getSize());
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        String filename = "/Users/admin/Downloads/pride-and-prejudice.txt";
        Set<String> bstSet = new BSTSet<>();
        double time1 = testSet(bstSet,filename);
        System.out.println("BST Set: " + time1 + " s");
        System.out.println();
        Set<String> linkedListSet = new LinkedListSet<>();
        double time2 = testSet(linkedListSet,filename);
        System.out.println("LinkedList Set: " + time2 + " s");
        System.out.println();
        Set<String> avlTreeSet = new AVLTreeSet<>();
        double time3 = testSet(avlTreeSet,filename);
        System.out.println("AVLTree Set: " + time3 + " s");
    }
}

测试结果

/Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同单词: 6530 BST Set: 0.153552536 s

/Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同单词: 6530 LinkedList Set: 2.292920811 s

/Users/admin/Downloads/pride-and-prejudice.txt 共有单词: 125901 共有不同单词: 6530 AVLTree Set: 0.057089254 s

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅析类装载 顶

    [Loaded com.guanjian.Parent from file:/E:/classload/out/production/classload/] ...

    算法之名
  • 归并排序算法 顶

    合并排序算法就是把多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表,则称为二路合并。

    算法之名
  • spring cloud zuul网关的作用

    zuul一般有两大作用,1是类似于Nginx的网址重定向,但zuul的重定向的一般是整个spring cloud里在Eureka注册中心的模块.

    算法之名
  • 数据结构 02

    在《数据结构 01》一文中,说到了数组、链表、栈以及队列这几种基本的线性结构,接下来就一起来看看剩下的内容。

    贪挽懒月
  • 萧峰与郭靖教你学会PHP的Trait

    章鱼喵
  • 洛谷P1291 [SHOI2002]百事世界杯之旅(期望DP)

    题目描述 “……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字,就可参加百事世界杯之旅的抽奖活动,获得球星背...

    attack
  • Codeforces Round #504 A. Single Wildcard Pattern Matching(思维)

    题目链接:http://codeforces.com/contest/1023/problem/A

    Ch_Zaqdt
  • 为了程序的健壮性,我们可以使用空对象模式

    在写代码的时候我们经常会遇到空指针,为了避免空指针的发生需要做一些判断。如果是复杂对象的话,还需要一层层地去判断。这个时候我就无比怀念groovy、kotlin...

    fengzhizi715
  • 首次回归,居然发这个!!!

    已经有好长时间没有发文章了,也不是懒,总想做一些安全方面的积累,再进行输出,这样的产出可能更有价值。

    七夜安全博客
  • SpringMVC源码深度解析之拦截器&过滤器&视图层&异步源码分析

    加入这个注解EnableWebMvc重复注入了WebMvcConfigurationSupport,会覆盖我们自定义的配置类

    须臾之余

扫码关注云+社区

领取腾讯云代金券