comments

difficulty

edit_url

3369. 设计数组统计跟踪器 🔒

English Version

题目描述

设计一个数据结构来跟踪它其中的值，并回答一些有关其平均值、中位数和众数的询问。

实现 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 只会在数据结构中至少有一个元素时被调用。

解法

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

我们定义一个队列 $\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$ 为添加的数字的数量。

Python3

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()

Java

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];
    }
}

C++

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;
    }
};

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

README.md

README.md

3369. 设计数组统计跟踪器 🔒

题目描述

解法

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

Python3

Java

C++

Go

Files

README.md

Latest commit

History

README.md

File metadata and controls

3369. 设计数组统计跟踪器 🔒

题目描述

解法

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

Python3

Java

C++

Go