🍁1. Set系列集合
Set
接口是一种不包含重复元素的集合。它继承自Collection
接口,所以可以使用Collection所拥有的方法,Set
接口的实现类主要有HashSet
、LinkedHashSet
、TreeSet
等,它们各自以不同的方式存储元素,但都遵循Set
接口的规定。
- 当你需要确保集合中的元素唯一时。
- 当你不需要保持元素的插入顺序时(除非使用
LinkedHashSet
)。
- 当你需要元素自然排序或根据自定义排序规则排序时(使用
TreeSet
)。
🍁1.1 HashSet
当用HashSet实例化对象时,由于底层结构是哈希表,所以元素是无序的,而TreeSet底层是红黑树,是有序的
由于Set系列集合里面不能有重复的元素,在之前我们也了解到,add方法的返回值是boolean类型的,当遇到重复元素,第二次添加就会添加失败
并且Set集合没有索引的概念,不能通过下标的方式进行遍历打印
和之前一样,没有索引的集合可以通过迭代器,增强for,lambda表达式进行遍历
Iterator<String> it = s1.iterator(); while (it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); for(String s : s1){ System.out.print(s + " "); } System.out.println(); s1.forEach(new Consumer<String>() { public void accept(String s) { System.out.print(s + " "); } });
🍁1.2 LinkedHashSet
LinkedHashSet底层也是哈希表,但是存取元素的顺序是一致的,因为使用了双向链表记录添加顺序
🍁1.3 TreeSet
TreeSet是基于红黑树实现的,TreeSet
中的元素处于排序状态,因此查找、添加、删除和遍历等操作都能以对数时间复杂度进行。但是,向TreeSet
中添加的元素必须实现Comparable
接口,或者在创建TreeSet
时提供一个Comparator
对象,以确保元素可以被正确地排序。
排序规则:Integer,Double等数值类型默认按照从小到大的顺序排序,对于字符,字符串类型,按照ASCII码表中的数字进行升排序
接下来演示一下,创建自定义类型的TreeSet
例如:给出一个Student类,要求按照学生的年龄排序
首先创建好Student类之后,需要实现Comparable接口,然后重写compareTo和toString方法
public class Student implements Comparable<Student>{ public String name; public int age; public Student(String name, int age) { this.name = name; this.age = age; } public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; } public int compareTo(Student o) { return this.age - o.age;//this.age表示要添加的元素 } }
this.age表示要添加的元素,所以如果返回值是负数,表示要添加的元素是小的,存左边,如果是0,表示元素已经存在,直接舍弃
public class Text2 { public static void main(String[] args) { Student s1 = new Student("zhang",18); Student s2 = new Student("wang",20); Student s3 = new Student("li",19); TreeSet<Student> treeSet = new TreeSet<>(); treeSet.add(s1); treeSet.add(s2); treeSet.add(s3); System.out.println(treeSet); } }
最终,虽然插入时没有按顺序,由于TreeSet底层是红黑树,所以最终也实现了排序的效果
比较器排序
问题:根据字符串长度比较,长度相同再按字典序比较
//o1:当前要添加的元素 //o2:红黑树中已经存在的元素 TreeSet<String> ts = new TreeSet<>(new Comparator<String>() { public int compare(String o1, String o2) { return (o1.length() - o2.length()) == 0 ? o1.compareTo(o2) : o1.length() - o2.length(); } }); ts.add("bbcd"); ts.add("abcde"); ts.add("abcd"); System.out.println(ts);
也就是在创建对象的时候传入比较器进行比较
🍁2. 单列集合的使用场景分析
介绍完Set系列集合之后,我们的单列集合就都学习完了,接下来分析一下这写集合的使用场景
如果集合中元素可重复:使用ArrayList(基于数组)
如果集合中元素可重复并且用到增删操作多余查询:使用LinkedList
如果需要对集合去重:使用HashSet
如果需要在去重的前提下还要保证存取顺序:使用LinkedHashSet
如果需要对集合中的元素进行排序:使用TreeSet
🍁3. Map系列集合
Map系列的集合称为双列集合
1. 双列集合一次存储一对数据,分别为键和值
2. 键不能重复,值可以重复
3. 键和值是一一对应的,每一个键都对应一个值
4. 键+值整体称为键值对,也叫Entry对象
和Set集合类似,Map是顶层接口,底下有这些实现类
以下就是Map集合常用的API
🍁3.1 HashMap
HashMap的底层也是哈希表,和之前的HashSet不同,HashMap中,当插入的key相同时,第二次插入会覆盖原来的value值,同时,如果存储的是自定义类型的对象还需要重写HashCode和equals方法
编辑其他方法就不演示了,下面来介绍一下map的遍历
Map的遍历
键找值:调用keySet方法,获取所有的key,把返回值放在Set集合中,再遍历Set集合,通过get方法获取每一个key的value
//获取所有的键,并放在Set集合中 Set<String> set = map.keySet(); //遍历set,根据所有的键获取值 for(String key:set){ int value = map.get(key); System.out.println(key + " = " + value); }
通过键值对对象进行遍历
调用entrySet方法,把所有键值对对象放在Set集合中,再遍历Set集合
可以看出,Entry是Map接口的一个内部接口,所以需要通过Map.Entry的形式调用,也可以直接导入
import java.util.Map.Entry;
就可以省略Map.
遍历时,可以直接打印Entry对象,也可以通过get的方式获取key和value
Set<Map.Entry<String, Integer>> entries = map.entrySet(); for(Map.Entry<String,Integer> entry : entries){ //System.out.println(entry); String s = entry.getKey(); Integer i = entry.getValue(); System.out.println(s + " = " + i); }
最后还可以通过lambda的形式遍历
map.forEach(new BiConsumer<String, Integer>() { public void accept(String key, Integer value) { System.out.println(key + " = " + value); } }); map.forEach((key, value) -> System.out.println(key + " = " + value));
🍁3.2 LinkedHashMap
和LinkedHashSet一样,LinkedHashMap存储的键是有序的(存储顺序和取出顺序一样)
🍁3.3 TreeMap
TreeMap和TreeSet底层一样,都是红黑树,根据键进行排序,排序规则也是类似的,对于非数值等类型,可以实现Comparable接口,指定比较规则,也可以传入比较器
🍁4. 面试OJ题练习
🍁4.1 随机链表的复制
也就是下面这种情况
如果说直接对链表节点进行复制是不可以的,因为题目中要求的是深拷贝,所以说拷贝后的 节点可能和原来的地址不一样
思路:遍历原来的链表,每遍历一次都创建一个新的节点,把原来的节点和拷贝的新节点的映射关系使用map存储起来,再通过get方法得到节点,再连接next和random
public Node copyRandomList(Node head) { Map<Node, Node> map = new LinkedHashMap<>(); Node cur = head; while (cur != null) { Node copy = new Node(cur.val); map.put(cur, copy); cur = cur.next; } /*cur = head; while (cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; }*/ Set<Node> keySet = map.keySet(); for (Node curNode : keySet) { map.get(curNode).next = map.get(curNode.next); map.get(curNode).random = map.get(curNode.random); } return map.get(head); }
🍁4.2 宝石与石头
这一题就可以很好的利用Set集合元素不能重复的特性了,如果不用Set集合,把全部元素异或一遍就可以找到了,而且速度更快,这里只是为了练习一下Set集合的使用,只需要把jewels存一个set,再遍历stones,判断是否有set集合里的元素即可
public class Text { public static void main(String[] args) { String jewels = "aA"; String stones = "aAABBBBB"; System.out.println(numJewelsInStones(jewels, stones)); } public static int numJewelsInStones(String jewels, String stones) { Set<Character> set = new HashSet<>(); for (int i = 0; i < jewels.length(); i++) { set.add(jewels.charAt(i)); } int cnt = 0; for (int i = 0; i < stones.length(); i++) { if (set.contains(stones.charAt(i))) { cnt++; } } return cnt; } }
🍁4.3 前k个高频单词
思路:前k个高频词,就是经典的topk问题,根据之前我们学到的,就是用小根堆解决,首先统计一下每个单词出现的频率,并通过map存储它们的映射关系,接着创建小根堆,套用之前的模板解决
public List<String> topKFrequent(String[] words, int k) { Map<String, Integer> map = new HashMap<>(); //统计单词个数并存入map for (String s : words) { if (map.get(s) == null) { map.put(s, 1); } else { int val = map.get(s); map.put(s, ++val); } } //创建根据map的value创建小根堆 PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() { public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { //相同时根据key创建大根堆,最后反转的时候就可以把字典序靠前的排到前面了 if (o1.getValue().compareTo(o2.getValue()) == 0) { return o2.getKey().compareTo(o1.getKey()); } return o1.getValue().compareTo(o2.getValue()); } }); //根据之前讲解的topk问题解决 for (Map.Entry<String, Integer> entry : map.entrySet()) { //先把前K个元素加入大根堆 if (minHeap.size() < k) { minHeap.offer(entry); } else { Map.Entry<String, Integer> top = minHeap.peek(); //堆顶元素频率小于后面的 if (top.getValue().compareTo(entry.getValue()) < 0) { minHeap.poll(); minHeap.offer(entry); } else if (top.getValue().compareTo(entry.getValue()) == 0) { //堆顶元素等于后面时,堆顶的key字典序大于后面的 if (top.getKey().compareTo(entry.getKey()) > 0) { minHeap.poll(); minHeap.offer(entry); } } } } ArrayList<String> ans = new ArrayList<>(); //把key存入ArrayList for (int i = 0; i < k; i++) { ans.add(minHeap.poll().getKey()); } //题目要求出现频率由高到低,进行翻转 Collections.reverse(ans); return ans; }