跳转至

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

解法

方法一：队列 + 哈希表 + 有序集合

我们定义一个队列 $\textit{q}$，用来存储添加的数字，一个变量 $\textit{s}$，用来存储所有数字的和，一个哈希表 $\textit{cnt}$，用来存储每个数字的出现次数，一个有序集合 $\textit{sl}$，用来存储所有数字，一个有序集合 $\textit{sl2}$，用来存储所有数字及其出现次数，按照出现次数降序、数值升序的顺序。

在 addNumber 方法中，我们将数字添加到队列 $\textit{q}$ 中，将数字添加到有序集合 $\textit{sl}$ 中，然后先将数字及其出现次数从有序集合 $\textit{sl2}$ 中删除，再更新数字的出现次数，最后将数字及其出现次数添加到有序集合 $\textit{sl2}$ 中，并更新所有数字的和。时间复杂度为 $O(\log n)$。

在 removeFirstAddedNumber 方法中，我们从队列 $\textit{q}$ 中删除最早添加的数字，从有序集合 $\textit{sl}$ 中删除数字，然后先将数字及其出现次数从有序集合 $\textit{sl2}$ 中删除，再更新数字的出现次数，最后将数字及其出现次数添加到有序集合 $\textit{sl2}$ 中，并更新所有数字的和。时间复杂度为 $O(\log n)$。

在 getMean 方法中，我们返回所有数字的和除以数字的数量，时间复杂度为 $O(1)$。

在 getMedian 方法中，我们返回有序集合 $\textit{sl}$ 中的第 $\textit{len}(\textit{q}) / 2$ 个数字，时间复杂度为 $O(1)$ 或 $O(\log n)$。

在 getMode 方法中，我们返回有序集合 $\textit{sl2}$ 中的第一个数字，时间复杂度 $O(1)$。

在 Python 中，我们可以直接按下标获取有序集合中的元素，在其它语言中，我们可以通过对顶堆实现。

空间复杂度 $O(n)$，其中 $n$ 为添加的数字的数量。

 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
40
41
42
43
44
45
from sortedcontainers import SortedList


class StatisticsTracker:

    def __init__(self):
        self.q = deque()
        self.s = 0
        self.cnt = defaultdict(int)
        self.sl = SortedList()
        self.sl2 = SortedList(key=lambda x: (-x[1], x[0]))

    def addNumber(self, number: int) -> None:
        self.q.append(number)
        self.sl.add(number)
        self.sl2.discard((number, self.cnt[number]))
        self.cnt[number] += 1
        self.sl2.add((number, self.cnt[number]))
        self.s += number

    def removeFirstAddedNumber(self) -> None:
        number = self.q.popleft()
        self.sl.remove(number)
        self.sl2.discard((number, self.cnt[number]))
        self.cnt[number] -= 1
        self.sl2.add((number, self.cnt[number]))
        self.s -= number

    def getMean(self) -> int:
        return self.s // len(self.q)

    def getMedian(self) -> int:
        return self.sl[len(self.q) // 2]

    def getMode(self) -> int:
        return self.sl2[0][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()

  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
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
class MedianFinder {
    private final PriorityQueue<Integer> small = new PriorityQueue<>(Comparator.reverseOrder());
    private final PriorityQueue<Integer> large = new PriorityQueue<>();
    private final Map<Integer, Integer> delayed = new HashMap<>();
    private int smallSize;
    private int largeSize;

    public void addNum(int num) {
        if (small.isEmpty() || num <= small.peek()) {
            small.offer(num);
            ++smallSize;
        } else {
            large.offer(num);
            ++largeSize;
        }
        rebalance();
    }

    public Integer findMedian() {
        return smallSize == largeSize ? large.peek() : small.peek();
    }

    public void removeNum(int num) {
        delayed.merge(num, 1, Integer::sum);
        if (num <= small.peek()) {
            --smallSize;
            if (num == small.peek()) {
                prune(small);
            }
        } else {
            --largeSize;
            if (num == large.peek()) {
                prune(large);
            }
        }
        rebalance();
    }

    private void prune(PriorityQueue<Integer> pq) {
        while (!pq.isEmpty() && delayed.containsKey(pq.peek())) {
            if (delayed.merge(pq.peek(), -1, Integer::sum) == 0) {
                delayed.remove(pq.peek());
            }
            pq.poll();
        }
    }

    private void rebalance() {
        if (smallSize > largeSize + 1) {
            large.offer(small.poll());
            --smallSize;
            ++largeSize;
            prune(small);
        } else if (smallSize < largeSize) {
            small.offer(large.poll());
            --largeSize;
            ++smallSize;
            prune(large);
        }
    }
}

class StatisticsTracker {
    private final Deque<Integer> q = new ArrayDeque<>();
    private long s;
    private final Map<Integer, Integer> cnt = new HashMap<>();
    private final MedianFinder medianFinder = new MedianFinder();
    private final TreeSet<int[]> ts
        = new TreeSet<>((a, b) -> a[1] == b[1] ? a[0] - b[0] : b[1] - a[1]);

    public StatisticsTracker() {
    }

    public void addNumber(int number) {
        q.offerLast(number);
        s += number;
        ts.remove(new int[] {number, cnt.getOrDefault(number, 0)});
        cnt.merge(number, 1, Integer::sum);
        medianFinder.addNum(number);
        ts.add(new int[] {number, cnt.get(number)});
    }

    public void removeFirstAddedNumber() {
        int number = q.pollFirst();
        s -= number;
        ts.remove(new int[] {number, cnt.get(number)});
        cnt.merge(number, -1, Integer::sum);
        medianFinder.removeNum(number);
        ts.add(new int[] {number, cnt.get(number)});
    }

    public int getMean() {
        return (int) (s / q.size());
    }

    public int getMedian() {
        return medianFinder.findMedian();
    }

    public int getMode() {
        return ts.first()[0];
    }
}

  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
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
class MedianFinder {
public:
    void addNum(int num) {
        if (small.empty() || num <= small.top()) {
            small.push(num);
            ++smallSize;
        } else {
            large.push(num);
            ++largeSize;
        }
        reblance();
    }

    void removeNum(int num) {
        ++delayed[num];
        if (num <= small.top()) {
            --smallSize;
            if (num == small.top()) {
                prune(small);
            }
        } else {
            --largeSize;
            if (num == large.top()) {
                prune(large);
            }
        }
        reblance();
    }

    int findMedian() {
        return smallSize == largeSize ? large.top() : small.top();
    }

private:
    priority_queue<int> small;
    priority_queue<int, vector<int>, greater<int>> large;
    unordered_map<int, int> delayed;
    int smallSize = 0;
    int largeSize = 0;

    template <typename T>
    void prune(T& pq) {
        while (!pq.empty() && delayed[pq.top()]) {
            if (--delayed[pq.top()] == 0) {
                delayed.erase(pq.top());
            }
            pq.pop();
        }
    }

    void reblance() {
        if (smallSize > largeSize + 1) {
            large.push(small.top());
            small.pop();
            --smallSize;
            ++largeSize;
            prune(small);
        } else if (smallSize < largeSize) {
            small.push(large.top());
            large.pop();
            ++smallSize;
            --largeSize;
            prune(large);
        }
    }
};

class StatisticsTracker {
private:
    queue<int> q;
    long long s = 0;
    unordered_map<int, int> cnt;
    MedianFinder medianFinder;
    set<pair<int, int>> ts;

public:
    StatisticsTracker() {}

    void addNumber(int number) {
        q.push(number);
        s += number;
        ts.erase({-cnt[number], number});
        cnt[number]++;
        medianFinder.addNum(number);
        ts.insert({-cnt[number], number});
    }

    void removeFirstAddedNumber() {
        int number = q.front();
        q.pop();
        s -= number;
        ts.erase({-cnt[number], number});
        cnt[number]--;
        if (cnt[number] > 0) {
            ts.insert({-cnt[number], number});
        }
        medianFinder.removeNum(number);
    }

    int getMean() {
        return static_cast<int>(s / q.size());
    }

    int getMedian() {
        return medianFinder.findMedian();
    }

    int getMode() {
        return ts.begin()->second;
    }
};

1

评论