2022-8-2 剑指offer-数据结构-哈希，列表

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

难度中等44收藏分享切换为英文接收动态反馈

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构：

• insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。
• remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false 。
• getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

 1 class RandomizedSet {
 2     Node head;
 3     Node tail;
 4     Map<Integer,Node> map;
 5     int size;
 6     /** Initialize your data structure here. */
 7     public RandomizedSet() {
 8         map=new HashMap<>();
 9         head=new Node();
10         tail=new Node();
11         head.next=tail;
12         tail.prev=head;
13         size=0;
14     }
15     
16     /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
17     public boolean insert(int val) {
18         if (map.containsKey(val)) return false;
19         Node temp=new Node(val);
20         addNode(temp);
21         map.put(val,temp);
22         size++;
23         //System.out.println(size);
24         return true;
25     }
26     
27     /** Removes a value from the set. Returns true if the set contained the specified element. */
28     public boolean remove(int val) {
29         if (!map.containsKey(val)) return false;
30         removeNode(map.get(val));
31         map.remove(val);
32         size--;
33         //System.out.println(size);
34         return true;
35     }
36     
37     /** Get a random element from the set. */
38     public int getRandom() {
39         //System.out.println("random"+size);
40         int index=new Random().nextInt(size)+1;
41         //System.out.println("random"+index);
42         return getNode(index).val;
43     }
44 
45     public void addNode(Node node){
46         node.prev=head;
47         node.next=head.next;
48         head.next.prev=node;
49         head.next=node;
50     }
51 
52     public void removeNode(Node node){
53         Node left=node.prev;
54         Node right=node.next;
55         left.next=right;
56         right.prev=left;
57     }
58 
59     public Node getNode(int index){
60         Node t=head;
61         for (int i=0;i<index;i++){
62             t=t.next;
63         }
64         return t;
65     }
66 }
67 
68 
69 class Node{
70     int val;
71     Node prev;
72     Node next;
73     Node(){
74 
75     }
76     Node(int val){
77         this.val=val;
78     }
79 }
80 
81 /**
82  * Your RandomizedSet object will be instantiated and called as such:
83  * RandomizedSet obj = new RandomizedSet();
84  * boolean param_1 = obj.insert(val);
85  * boolean param_2 = obj.remove(val);
86  * int param_3 = obj.getRandom();
87  */

思路：实现思路是哈希记录节点的位置，哈希判断集合是否重复，双向链表实现变长的数组，随机返回的时间复杂度较高。

哈希加列表的实现的主要思想是 记录元素的索引位置，在去除元素时，将列表的最后一个与当前位置互换，再去掉最后的数据，这样不会影响其余元素的索引。