【数据结构】Map和Set

目录

一、Map

1.1 Map常用方法

1.2 Map注意事项

1.3 Map的遍历

二、Set

2.1 Set常用方法

2.2 Set注意事项

2.3 Set的遍历

三、题目练习

3.1 从给定的数据中，找出第一个重复的数据

3.2 去除给定的数据中重复的数据

3.3 统计重复的数据出现的次数

3.4 只出现一次的数据

3.5 复制带随机指针的链表

3.6 宝石与石头

3.7 坏键盘打字

3.8 前K个高频单词

---

一、Map

1.1 Map常用方法

Map是一个接口类，没有继承Collection。存储的是键值对，键一定是唯一的，不能重复。

1.2 Map注意事项

• Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
• Map中存放键值对的Key是唯一的， value是可以重复的
• Map中的Key可以全部分离出来,存储到Set中来进行访问(因为Key不能重复)。
• Map中的value可以全部分离出来,存储在Collection的任何-个子集合中(value可能有重复)。
• Map中键值对的Key不能直接修改, value可以修改，如果要修改key,只能先将该key删除掉,然后再来进行重新插入
• key可以为null。value也可以为null

1.3 Map的遍历

借助Set> entrySet()

        Set> entrySet = hashmap.entrySet();
        for(Map.Entry entry : entrySet){
            int a = entry.getKey();
            System.out.println(entry);
        }

二、Set

2.1 Set常用方法

2.2 Set注意事项

• Set是继承自Collection的一 个接口类
• Set中只存储了key, 并组要求key一定要唯一
• Set最大的功能就是对集合中的元素进行去重
• Set中的Key不能修改，如果要修改,先将原来的删除掉,然后再重新插入
• 插入的值可以为null

2.3 Set的遍历

    public static void main(String[] args) {
        HashSet set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

三、题目练习

3.1 从给定的数据中，找出第一个重复的数据

    public int func(int[] nums){
        Set hashSet = new HashSet<>();
        for(int i=0;i
            if(hashSet.contains(nums[i])){
                return nums[i];
            }
            hashSet.add(nums[i]);
        }
        return -1;
    }

3.2 去除给定的数据中重复的数据

    public void func2(int[] nums){
        Set hashSet = new HashSet<>();
        for(int i=0;i
            hashSet.add(nums[i]);
        }
        System.out.println(hashSet);
    }

3.3 统计重复的数据出现的次数

    public void fun3(int[] nums){
        Map hashmap = new HashMap<>();
   
        for (int i = 0; i < nums.length; i++) {
            if(hashmap.containsKey(nums[i])){
                // 如果在hashmap中存在，就更新次数
                int count = hashmap.get(nums[i]);
                count = count+1;
                hashmap.put(nums[i],count);
            }else{
                // 不存在，就放入hashmap中，值是1
                hashmap.put(nums[i],1);
            }
        }
        Set> entrySet = hashmap.entrySet();
        // 遍历hashmap
        for(Map.Entry entry : entrySet){
            int a = entry.getKey();
            System.out.println(entry);
        }
    }

3.4 只出现一次的数据

力扣

class Solution {
    public int singleNumber(int[] nums) {
        Set set = new HashSet<>();
        for(int i=0;i
            // 如果已经出现，就从set中移除该元素
            if(set.contains(nums[i])){
                set.remove(nums[i]);
            }else{
                set.add(nums[i]);
            }
        }
        // set剩下的元素就是只出现一次的元素
        Iterator it = set.iterator();
        
        while(it.hasNext()){
            return it.next();
        }
        return -1;
    }
}

3.5 复制带随机指针的链表

力扣

class Solution {
    public Node copyRandomList(Node head) {
        Map map = new HashMap<>();
        Node cur = head;
        while(cur != null){
            // 将新节点和旧节点的对应关系存储到map中
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            // 得到新节点
            // 从map中得到新节点和旧节点 根据旧节点的next和random属性修改新节点的属性
            Node node = map.get(cur);
            node.next = map.get(cur.next);
            node.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

3.6 宝石与石头

力扣

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set set = new HashSet<>();
        for(int i =0;i
            char ch = jewels.charAt(i);
            // 对jewels中的字符进行去重
            if(!set.contains(ch)){
                set.add(ch);
            }
        }
        int sum = 0;
        for(int i =0;i
            char ch = stones.charAt(i);
            // stones中的字符如果在set中出现，sum++
            if(set.contains(ch)){
                sum++;
            }
        }
        return sum;
    }
}

3.7 坏键盘打字

旧键盘 (20)__牛客网

import java.util.*;
public class Main{
    public static void func(String str1,String str2){
        // 先将字符串转成大写的字符数组
        char[] ch1 = str1.toUpperCase().toCharArray();
        char[] ch2 = str2.toUpperCase().toCharArray();
        // ch1是正常的输入
        // ch2是实际的输入
        Set set1 = new HashSet<>();
        for(char ch:ch2){
            // 统计ch2中出现的不重复的字符 ，这些字符都是好的按键
            if(!set1.contains(ch)){
                set1.add(ch);
            }
        }
        Set set2 = new HashSet<>();
        for(char ch:ch1){
            // 如果字符没有在好的按键集合里，就加到set2中，加之前要判断是否已经存在，如果存在，就不用再add了
            if(!set1.contains(ch)){
                if(!set2.contains(ch)){
                    set2.add(ch);
                    System.out.print(ch);
                 
                }
            }
        }
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        func(str1,str2);
    }
}

3.8 前K个高频单词

力扣

• 先统计每个单词的出现次数
• 建立一个小根堆，重写compare方法。存在两种情况，第一种是两个词的出现次数一样，比较单词的首字母的AscII码值。第二种情况是两个词的出现次数不一样
• topK思想。

class Solution {
    public List topKFrequent(String[] words, int k) {
        int c = k;
        HashMap hashmap = new HashMap<>();
        // 统计每个单词的出现次数
        for(String str:words){
            if(!hashmap.containsKey(str)){
                hashmap.put(str,1);
            }else{
                int count = hashmap.get(str);
                hashmap.put(str,count+1);
            }
        }
        // 建立一个小根堆，重写compare方法
        PriorityQueue> queue = new PriorityQueue<>(new Comparator>(){
            @Override
            public int compare(Map.Entry o1,Map.Entry o2){
                if(o1.getValue().equals(o2.getValue())){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });
        // topK的思想
        for(Map.Entry entry : hashmap.entrySet()){
            if(k >0){
                queue.offer(entry);
                k--;
            }else{
                Map.Entry peek = queue.peek();
                int tmp = peek.getValue().compareTo(entry.getValue());
                if(tmp < 0){
                    queue.poll();
                    queue.offer(entry);
                }else if(tmp == 0){
                    if(peek.getKey().compareTo(entry.getKey()) >0 ){
                        queue.poll();
                        queue.offer(entry);                       
                    }
                }
            }
        }
        List result = new ArrayList<>();
        for(int i=0;i
            result.add(queue.poll().getKey());
        }
        Collections.reverse(result);
        return result;
    }
}