@ninijia 在 Leetcode每日一题练习 ------ 432. 全 O(1) 的数据结构 中发帖
从Leetcode 每日一题练习继续讨论:
432. 全 O(1) 的数据结构
432. All O`one Data Structure
题解
本题是一道难题,本题要快速获得出现频率最大的key和出现频率最小的key,就要将频率和对应的key记录下来。一方面我们要记录每个key和其对应的频率方便进行增减操作,即尽快完成inc和dec操作,另一方面我们也要记录不同频率和其对应的keys以便快速查找最大最小频率对应的key。记录每个key和其对应的频率可以通过map(可以使用unordered map,因为顺序不重要)实现,记录频率和其对应的key也可以通过map实现,区别在于因为一个频率可能对应多个字符串,则map需要将频率作为键,将一个字符串set作为值方便快速插入和删除该频率对应的字符串中的某个字符串。由于map默认是有序的,则找到最大值和最小值只需返回map的开头和结尾set中...