Leetcode 3369 (设计数组统计跟踪器)
设计一个数据结构来跟踪它其中的值，并回答一些有关其平均值、中位数和众数的询问。
实现 StatisticsTracker 类。
StatisticsTracker()：用空数组初始化 StatisticsTracker 对象。
void addNumber(int number)：将 number 添加到数据结构中。
void removeFirstAddedNumber()：从数据结构删除最早添加的数字。
int getMean()：返回数据结构中数字向下取整的 平均值。
int getMedian()：返回数据结构中数字的 中位数。
int getMode()：返回数据结构中数字的 众数。如果有多个众数，返回最小的那个。
注意：
数组的 平均值 是所有值的和除以数组中值的数量。
数组的 中位数 是在非递减顺序排序后数组的中间元素。如果中位数有两个选择，则取两个值中较大的一个。
数组的 众数 是数组中出现次数最多的元素。
示例 1：
输入：
["StatisticsTracker", "addNumber", "addNumber", "addNumber", "addNumber", "getMean", "getMedian", "getMode", "removeFirstAddedNumber", "getMode"]
[[], [4], [4], [2], [3], [], [], [], [], []]
输出：
[null, null, null, null, null, 3, 4, 4, null, 2]
解释：
StatisticsTracker statisticsTracker = new StatisticsTracker();
statisticsTracker.addNumber(4); // 现在数据结构中有 [4]
statisticsTracker.addNumber(4); // 现在数据结构中有 [4, 4]
statisticsTracker.addNumber(2); // 现在数据结构中有 [4, 4, 2]
statisticsTracker.addNumber(3); // 现在数据结构中有 [4, 4, 2, 3]
statisticsTracker.getMean(); // return 3
statisticsTracker.getMedian(); // return 4
statisticsTracker.getMode(); // return 4
statisticsTracker.removeFirstAddedNumber(); // 现在数据结构中有 [4, 2, 3]
statisticsTracker.getMode(); // return 2
示例 2：
输入：
["StatisticsTracker", "addNumber", "addNumber", "getMean", "removeFirstAddedNumber", "addNumber", "addNumber", "removeFirstAddedNumber", "getMedian", "addNumber", "getMode"]
[[], [9], [5], [], [], [5], [6], [], [], [8], []]
输出：
[null, null, null, 7, null, null, null, null, 6, null, 5]
解释：
StatisticsTracker statisticsTracker = new StatisticsTracker();
statisticsTracker.addNumber(9); // 现在数据结构中有 [9]
statisticsTracker.addNumber(5); // 现在数据结构中有 [9, 5]
statisticsTracker.getMean(); // return 7
statisticsTracker.removeFirstAddedNumber(); // 现在数据结构中有 [5]
statisticsTracker.addNumber(5); // 现在数据结构中有 [5, 5]
statisticsTracker.addNumber(6); // 现在数据结构中有 [5, 5, 6]
statisticsTracker.removeFirstAddedNumber(); // 现在数据结构中有 [5, 6]
statisticsTracker.getMedian(); // return 6
statisticsTracker.addNumber(8); // 现在数据结构中有 [5, 6, 8]
statisticsTracker.getMode(); // return 5
提示：
1 <= number <= 10**9
addNumber，removeFirstAddedNumber，getMean，getMedian 和 getMode 的总调用次数最多为 10**5。
removeFirstAddedNumber，getMean，getMedian 和 getMode 只会在数据结构中至少有一个元素时被调用。
Python题解
from sortedcontainers import SortedList
from sortedcontainers import SortedDict
class StatisticsTracker:
def __init__(self):
self.num = SortedList([])
self.d = SortedDict()
self.n = 0
self.h = SortedDict()
self.x = SortedDict()
def addNumber(self, number: int) -> None:
self.num.add(number)
self.d[self.n] = number
if number not in self.h.keys():
self.h[number] = 1
if self.h[number] not in self.x.keys():
self.x[self.h[number]] = SortedList([])
self.x[self.h[number]].add(number)
else:
self.x[self.h[number]].add(number)
else:
if self.h[number] in self.x.keys():
self.x[self.h[number]].remove(number)
if len(self.x[self.h[number]]) == 0:
self.x.pop(self.h[number])
self.h[number] += 1
if self.h[number] not in self.x.keys():
self.x[self.h[number]] = SortedList([])
self.x[self.h[number]].add(number)
else:
self.x[self.h[number]].add(number)
self.n += 1
def removeFirstAddedNumber(self) -> None:
b = self.d.popitem(0)
self.num.remove(b[1])
self.x[self.h[b[1]]].remove(b[1])
if len(self.x[self.h[b[1]]]) == 0:
self.x.pop(self.h[b[1]])
m = self.h[b[1]] - 1
if m not in self.x.keys():
self.x[m] = SortedList([])
self.x[m].add(b[1])
else:
self.x[m].add(b[1])
self.h[b[1]] -= 1
def getMean(self) -> int:
return math.floor(sum(self.num)/len(self.num))
def getMedian(self) -> int:
if len(self.num)%2 == 1:
return self.num[len(self.num)//2]
else:
return max(self.num[len(self.num)//2],self.num[len(self.num)//2-1])
def getMode(self) -> int:
return self.x[self.x.keys()[-1]][0]
# Your StatisticsTracker object will be instantiated and called as such:
# obj = StatisticsTracker()
# obj.addNumber(number)
# obj.removeFirstAddedNumber()
# param_3 = obj.getMean()
# param_4 = obj.getMedian()
# param_5 = obj.getMode()
