3369：设计数组统计跟踪器（★★）

Ian

2024-11-30 约 961 字预计阅读 2 分钟次阅读

力扣第 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⁹
addNumber，removeFirstAddedNumber，getMean，getMedian 和 getMode 的总调用次数最多为 10⁵。
removeFirstAddedNumber，getMean，getMedian 和 getMode 只会在数据结构中至少有一个元素时被调用。

分析

队列维护数的添加删除顺序
有序集合维护数的中位数
哈希表维护每个数字的频数
另一个有序集合维护 <频数、数> 的对，次数相同时要返回最小的数，因此维护 <频数、数的负>

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


from sortedcontainers import SortedList
class StatisticsTracker:

    def __init__(self):
        self.A = deque()
        self.sl = SortedList()
        self.ct = defaultdict(int)
        self.sl2 = SortedList()
        self.s = 0
        
    def addNumber(self, number: int) -> None:
        self.A.append(number)
        self.sl.add(number)
        self.s += number
        w = self.ct[number]
        if w:
            self.sl2.remove((w,-number))
        self.ct[number] = w+1
        self.sl2.add((w+1,-number))

    def removeFirstAddedNumber(self) -> None:
        x = self.A.popleft()
        self.sl.remove(x)
        self.s -= x
        w = self.ct[x]
        self.sl2.remove((w,-x))
        self.ct[x] -= 1
        if w>1:
            self.sl2.add((w-1,-x))
        
    def getMean(self) -> int:
        return self.s//len(self.A)
        
    def getMedian(self) -> int:
        n = len(self.sl)
        return self.sl[n//2]

    def getMode(self) -> int:
        return -self.sl2[-1][1]

1120 ms

目录

3369：设计数组统计跟踪器（★★）

题目

分析

解答