Fork me on GitHub

数据结构之集合和映射

发表于 | 分类于 | |

集合是承载元素的容器，每个元素只能存在一次，映射，在定义域中每一个值在值域都有一个值与他对应，存储(键，值)数据对的数据结构（Key，Value），根据键(Key)，寻找值(Value)

集合

基于二分搜索树的集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BST<E extends Comparable<E>>
{
    private class Node
    {
        public E e;
        public Node left,right;

        public Node(E e)
        {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;
    public BST()
    {
        root=null;
        size=0;
    }
    public int size()
    {
        return size;
    }
    public boolean isEmpty()
    {
        return size == 0;
    }
    //向二分搜索树中添加新的元素e
    public void add(E e)
    {
       root = add(root,e);
    }
    //向以node为根的二分搜索树种插入元素E。递归算法
    //返回插入新节点后二分搜索树的根
    private Node add(Node node,E e)
    {
        if(node == null)
        {
            size++;
            return new Node(e);
        }
        if(e.compareTo(node.e)<0)

            node.left = add(node.left,e);
        else if (e.compareTo(node.e) > 0 )
            node.right = add(node.right,e);
        return node;
    }

    public boolean contain(E e)
    {
        return contains(root,e);
    }
    //看以node为根的二分搜索树中是否包含元素e，递归算法
    private boolean contains(Node node,E e)
    {
        if(node == null)
            return false;
        if(e.compareTo(node.e) == 0)
            return true;
        else if(e.compareTo(node.e)<0)
            return contains(node.left,e);
        else //if(e.compareTo(node.e)>0)
            return contains(node.right,e);
    }

    //二分搜索树的前序遍历
    public void preOrder()
    {
        preOrder(root);
    }
    //前序遍历以node为根的二分搜索树，递归算法
    private void preOrder(Node node)
    {
        if(node == null)
            return;
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }
    //二分搜索树非递归前序遍历
    public void preOrderNR()
    {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty())
        {
            Node cur = stack.pop();
            System.out.println(cur.e);

            if(cur.right != null)
                stack.push(cur.right);
            if(cur.left != null)
                stack.push(cur.left);
        }
    }

    public void inOrder()
    {
        inOrder(root);
    }
    private void inOrder(Node node)
    {
        if(node==null)
            return;
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    public void postOrder()
    {
        postOrder(root);
    }
    private void postOrder(Node node)
    {
        if(node==null)
            return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    //二分搜索树的层序遍历
    public void levelOrder()
    {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty())
        {
            Node cur = q.remove();
            System.out.println(cur.e);

            if(cur.left != null)
                q.add(cur.left);
            if(cur.right != null)
                q.add(cur.right);
        }
    }

    //寻找二分搜索树的最小元素
    public E minimum()
    {
        if(size == 0)
            throw new IllegalArgumentException("BST is empty");
        return minimum(root).e;
    }
    //返回以node为根的二分搜索树的最小键值所在的结点
    private Node minimum(Node node)
    {
        if(node.left == null)
            return node;
        return minimum(node.left);
    }
    //寻找二分搜索树的最大元素
    public E maximum()
    {
        if(size == 0)
            throw new IllegalArgumentException("BST is empty");
        return maximum(root).e;
    }
    //返回以node为根的二分搜索树的最小键值所在的结点
    private Node maximum(Node node)
    {
        if(node.right == null)
            return node;
        return maximum(node.right);
    }
    //从二分搜索树中删除最小值所在结点，返回最小值
    public E removeMin()
    {
        E ret = minimum();
        root =  removeMin(root);
        return ret;
    }
    //删除掉以node为根的二分搜索树中的最小结点
    //返回删除结点后新的二分搜索树的根
    private Node removeMin(Node node)
    {
        if(node.left == null)
        {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }
    //从二分搜索树中删除最大值所在结点，返回最大值
    public E removeMax()
    {
        E ret = maximum();
        root =  removeMax(root);
        return ret;
    }
    //删除掉以node为根的二分搜索树中的最大结点
    //返回删除结点后新的二分搜索树的根
    private Node removeMax(Node node)
    {
        if(node.right == null)
        {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMin(node.right);
        return node;
    }
    //从二分搜索树中删除元素为e的结点
    public void remove(E e)
    {
        root = remove(root,e);
    }
    //删除掉以node为根的二分搜索树种值为e的结点，递归算法
    //返回删除结点后新的二分搜索树的根
    private Node remove(Node node, E e)
    {
        if(node == null)
            return null;
        if(e.compareTo(node.e)<0)
        {
            node.left = remove(node.left,e);
            return node;
        }
        else if(e.compareTo(node.e)>0)
        {
            node.right = remove(node.right,e);
            return node;
        }
        else
        {//e == node.e
            //待删除结点左子树为空的情况
            if(node.left == null)
            {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            //待删除结点右子树为空的情况
            if(node.right == null)
            {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //待删除结点左右子树均不为空的情况
            //找到比待删除结点大的最小结点，即待删除结点右子树的最小结点
            //用这个结点顶替待删除结点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }

    @Override
    public String toString()
    {
        StringBuilder res = new StringBuilder();
        generateBSTString(root,0,res);
        return res.toString();
    }
    //生成以node为根结点，深度为depth的描述二叉树的字符串
    private void generateBSTString(Node node,int depth,StringBuilder res)
    {
        if(node == null)
        {
            res.append(generateDepthString(depth)+"null\n");
            return;
        }
        res.append(generateDepthString(depth)+node.e+"\n");
        generateBSTString(node.left,depth+1,res);
        generateBSTString(node.right,depth+1,res);
    }
    private String generateDepthString(int depth)
    {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++)
            res.append("——");
        return res.toString();
    }
}
1
2
3
4
5
6
7
8
9
public interface Set<E>
{
    void add(E e);
    void remove(E e);
    boolean contain(E e);
    int getSize();
    boolean isEmpty();

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class BSTSet<E extends Comparable<E>> implements Set<E>
{
    private BST<E> bst;
    public BSTSet()
    {
        bst = new BST<E>();
    }

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

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

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

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


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

}

基于链表的集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class LinkedListSet<E> implements Set<E>
{
    private LinkedList<E> list;
    public LinkedListSet()
    {
        list = new LinkedList<E>();
    }


    @Override
    public void add(E e)
    {
        if(!list.contains(e))
            list.addFirst(e);

    }

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

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

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

    @Override
    public boolean isEmpty()
    {
        return list.isEmpty();
    }
}
集合的时间复杂度
LinkedListSet(基于链表) BSTSet(基于二分搜索树) 平均 最差
增 add O(n) O(h)———————————>O(logn)————O(n)
查 contains O(n) O(h)———————————>O(logn)————O(n)
删 remove O(n) O(h)———————————>O(logn)————O(n)

复杂度比较：

最差情况，退化成链表，和链表复杂度一致，解决方法：平衡二叉树

唯一摩尔斯密码词（leecode）

国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如: “a” 对应 “.-“, “b” 对应 “-…”, “c” 对应 “-.-.”, 等等。所有26个英文字母对应摩尔斯密码表如下：

给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，”cab” 可以写成 “-.-..–…”，(即 “-.-.” + “-…” + “.-“字符串的结合)。我们将这样一个连接过程称作单词翻译。返回我们可以获得所有词不同单词翻译的数量。

1
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution
{
    public int uniqueMorseRepresentations(String[] words)
    {
        String []  codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

        TreeSet<String> set = new TreeSet<>();
        for(String word:words)
        {
            StringBuilder res = new StringBuilder();
            for(int i=0;i<word.length();i++)

                res.append(codes[word.charAt(i)-'a']);
            set.add(res.toString());
        }
        return set.size();
    }
}

映射

基于LinkedList的映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package map;
public class LinkedListMap<K,V> implements Map<K,V>
{
    private class Node
    {
        public K key;
        public V value;
        public Node next;

        public Node(K key ,V value, Node next)
        {
            this.key = key;
            this.value = value;
            this.next = next;
        }

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

        public Node()
        {
            this(null, null,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.next = new Node(key,value,dummyHead);
            size++;
        }
        else
        node.value = value;
    }

    @Override
    public V remove(K key)
    {
        Node prev = dummyHead;
        while(prev.next != null)
        {
            if(prev.next.key.equals(key))
                break;
            prev = prev.next;
        }
        if(prev.next != null)
        {
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
            return delNode.value;
        }
        return null;
    }

    @Override
    public boolean contains(K key)
    {
        return getNode(key) != null;
    }

    @Override
    public V get(K key)
    {
        Node node = getNode(key);
        return node == null?null:node.value;
    }

    @Override
    public void set(K key, V newValue)
    {
        Node node = getNode(key);
        if(node == null)
            throw new IllegalArgumentException(key+"doesn't exist!");
        node.value = newValue;
    }

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

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

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

基于二分搜索树的映射实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
package map;


import BST.BST;

/**
 * @author zqnh
 * @date 2019/8/4 on 10:44.
 */
public class BSTMap<K extends Comparable<K>,V> implements Map<K,V>
{
    private class Node
    {
        public K key;
        public V value;
        public Node left,right;
        public Node(K key,V value)
        {
            this.key=key;
            this.value = value;
            left=null;
            right=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.key)<0)

            node.left = add(node.left,key,value);
        else if (key.compareTo(node.key) > 0 )
            node.right = add(node.right,key,value);
        else
            node.value = value;
        return node;
    }

    @Override
    public V remove(K key)
    {
        Node node = getNode(root,key);
        if(node!=null)
        {
            root = remove(root,key);
            return node.value;
        }
        return null;
    }
    //删除掉以node为根的二分搜索树中键为key的结点，递归算法
    //返回删除结点后新的二分搜索树的根
    private Node remove(Node node, K key)
    {
        if(node == null)
            return null;
        if(key.compareTo(node.key)<0)
        {
            node.left = remove(node.left,key);
            return node;
        }
        else if(key.compareTo(node.key)>0)
        {
            node.right = remove(node.right,key);
            return node;
        }
        else
        {//e == node.e
            //待删除结点左子树为空的情况
            if(node.left == null)
            {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            //待删除结点右子树为空的情况
            if(node.right == null)
            {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //待删除结点左右子树均不为空的情况
            //找到比待删除结点大的最小结点，即待删除结点右子树的最小结点
            //用这个结点顶替待删除结点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }
    private Node minimum(Node node)
    {
        if(node.left == null)
            return node;
        return minimum(node.left);
    }
    //删除掉以node为根的二分搜索树中的最小结点
    //返回删除结点后新的二分搜索树的根
    private Node removeMin(Node node)
    {
        if(node.left == null)
        {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }
    @Override
    public boolean contains(K key)
    {
        return getNode(root,key)!=null;
    }

    @Override
    public V get(K key)
    {
        Node node = getNode(root,key);
        return node == null?null:node.value;
    }

    @Override
    public void set(K key, V newValue)
    {
        Node node = getNode(root,key);
        if(node == null)
            throw new IllegalArgumentException(key+"doesn't exist");
        node.value= newValue;
    }

    @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.key) == 0)
            return node;
        else if(key.compareTo(node.key)<0)
            return getNode(node.left,key);
        else
            return getNode(node.right,key);
    }
}
LinkedListMap BSTMap 平均
增 add O(n) O(h) O(logn) O(n)
删 remove O(n) O(h) O(logn) O(n)
改 set O(n) O(h) O(logn) O(n)
查 get O(n) O(h) O(logn) O(n)
查 contains O(n) O(h) O(logn) O(n)

两个数组的交集leecode

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.ArrayList;
import java.util.TreeSet;

public class Solution
{
    public int[] intersection(int[] nums1, int[] nums2)
    {
        TreeSet<Integer> set = new TreeSet<>();
        for(int num:nums1)
            set.add(num);//已经全添加完了
        ArrayList<Integer> list = new ArrayList<>();
        for(int num:nums2)
            if(set.contains(num))
            {
                list.add(num);
                set.remove(num);//防止下一回碰到相同元素，移除后，就contains false
            }
        int [] res = new int [list.size()];
            for(int i=0;i<list.size();i++)
                res[i] = list.get(i);
            return res;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.util.ArrayList;
import java.util.TreeMap;


public class Solution
{
    public int[] intersect(int[] nums1, int[] nums2)
    {
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int num:nums1)
        {
            if(!map.containsKey(num))
                map.put(num,1);
            else
                map.put(num,map.get(num)+1);
        }
        ArrayList<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 [] res = new int[list.size()];
        for (int i = 0; i <list.size() ; i++)
            res[i] = list.get(i);
        return res;
        
    }
}