题目分析

设计题目也是面试的重点，这不仅仅考察小伙伴们的算法能力，思为能力，还考察小伙伴们对数据结构的掌握能力。这种题目难度往往不大，通过已有的一些数据结构加以变化，那么采用哪些已有的数据结构是这种题型的难点。

哈希表

这里要求我们以$O(1)$的时间复杂度完成插入，移除和随机获取操作。

首先分析题目的意思，如果要以$O(1)$插入和获取，可以通过列表完成，题目不要求集合中元素的顺序，因此直接尾插元素即可，获取时可以随机索引获得元素。但是移除时，时间复杂度是$O(n)$的。

如果要以$O(1)$插入和移除，可以通过哈希表完成，但是随机获取元素时，因为哈希表中的元素只能出现一次，所以无法保证返回元素的概率与其数量线性相关。

发现列表移除元素时间复杂度过高，是因为移除的元素并不一定在末尾，如果每次移除的元素都在末尾，那么可以实现以$O(1)$移除元素。如何保证每次移除的元素都在列表末尾？我们可以通过交换该元素与最后一个元素出现的位置，使用一个字典记录每个元素出现的位置。如列表为[1, 2, 3, 4, 5]，我们要移除3这个元素，我们先将3和5进行调换，然后移除最后的元素3即可。

要注意如果要移除的元素已经在末尾，则不需要调换，直接移除最后一个元素即可。如果要移除的元素不在末尾，要将末尾的元素的索引改为要移除元素的索引，将列标中对应位置的元素改为末尾元素。

还要注意，使用字典记录每个元素出现的位置时，字典中的键为元素值，字典中的值是一个哈希表，为什么要使用哈希表？是因为修改末尾元素的索引时，通过移除和添加操作的时间复杂度为$O(1)$，如果使用列表，那么要查找末尾元素的索引，然后进行修改，时间复杂度为$O(n)$

这个题目的关键是移除操作，代码并不难理解，小伙伴们认真想一想其中的逻辑关系。

from collections import defaultdict
from random import choice


class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lis = []
        self.dic = defaultdict(set)


    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        self.dic[val].add(len(self.lis))
        self.lis.append(val)
        return len(self.dic[val]) == 1


    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        if len(self.dic[val]) > 0:
            idx = self.dic[val].pop()
            if idx == len(self.lis) - 1:
                self.lis.pop()
            else:
                val1 = self.lis.pop()
                self.lis[idx] = val1
                self.dic[val1].remove(len(self.lis))
                self.dic[val1].add(idx)
            return True
        return False


    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        return choice(self.lis)

刷题总结

设计题是非常有趣的，也比较贴近于生活的实际应用，也许刚刚开始接触这种题型不太适应，多见识一些题目就会变得越来越强。