《程序员面试金典（第6版）》面试题 10.10. 数字流的秩

题目描述

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

• 实现 track(int x) 方法，每读入一个数字都会调用该方法；

• 实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

注意：本题相对原题稍作改动

示例:

输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]

提示：

• x <= 50000
• track 和 getRankOfNumber 方法的调用次数均不超过 2000 次

解题思路与代码

这道题，其实有一种特别简单的做法，和一个需要你有一定知识储备的做法，前者是我自己想出来的，时间复杂度偏高，但是空间复杂度比较低。后者呢？时间复杂度偏低，但是空间复杂度缺偏高，可以说，各有优点吧。

对于后者，用到了一种叫做树状数组的数据结构，你也可以理解为一种算法的思想，或者技巧。掌握这种数据结构的过程可能比较难，你首先得知道树状数组是个什么东西，才能知道里面的操作为什么这么去做。

那我们就一步一步的来，教会大家如何用这两种方法，来解决这道题！

方法1，使用sort函数帮助我们排序。

• 顾名思义，我们用一个vector数组来帮助我们去存储数据。

• 每次读取一个数字，我们就把这个数据添加到数组的最后面，然后对整个数组进行排序（用sort函数排序）

• 这样，track方法就编写完成啦。

• 紧接着，我们来编写一下getRankOfNumber方法，其实这个方法的实现也很简单。因为我们已经把读到的所有元素进行排序了，这个时候，只需要从后往前去遍历整个数组，找到第一个小于等于x的元素，返回这个元素的下标 + 1，就行了。如果找不到这样的元素，那就返回0就好啦。两个方法其实都不难的

具体的代码如下：

class StreamRank {
public:vector<int> vec;StreamRank() {}void track(int x) {vec.push_back(x);sort(vec.begin(),vec.end());}int getRankOfNumber(int x) {int pre = vec.size;for(int i = vec.size()-1; i >=0; --i){if(vec[i] <= x){pre = i;return pre + 1;}}return 0;}
};/*** Your StreamRank object will be instantiated and called as such:* StreamRank* obj = new StreamRank();* obj->track(x);* int param_2 = obj->getRankOfNumber(x);*/

复杂度分析

对于给出的 StreamRank 类，我们可以分析其方法的时间复杂度和空间复杂度如下：

track 方法：

• 时间复杂度：在每次调用 track 方法时，都会对 vec 进行排序。C++ 标准库中的 sort 函数的平均时间复杂度为 O(nlogn)，其中 n 是数组的长度。因此，track 方法的时间复杂度为 O(nlogn)。
• 空间复杂度：track 方法中，除了向 vec 添加元素外，没有使用额外的空间。因此，空间复杂度为 O(1)。

getRankOfNumber 方法：

• 时间复杂度：在最坏情况下，getRankOfNumber 方法需要遍历整个 vec。因此，它的时间复杂度为 O(n)，其中 n 是数组的长度。
• 空间复杂度：getRankOfNumber 方法中没有使用额外的空间，所以空间复杂度为 O(1)。
  StreamRank 类的总空间复杂度：

StreamRank 类中使用了一个 vector 容器来存储元素，其空间复杂度为 O(n)，其中 n 是存储的元素个数。

总结：StreamRank 类的时间复杂度主要取决于 track 方法的 O(n*logn)，而空间复杂度主要取决于存储元素的 vector，为 O(n)。

方法二，使用树状数组来解决问题

首先，请允许在下为大家讲解一下到底什么才是树状数组。树状数组的特点是什么？

• 树状数组是一种用于维护数列前缀和的数据结构，它可以在 O(logn) 的时间复杂度内修改单个元素的值，以及查询某个区间的元素和。

• 树状数组的特点其实就是，在单点修改 ，和区间查询，它所需要写的代码量少，与时间复杂度低而闻名。

• 但是树状数组需要的空间复杂度很高，原因是，假如我们的查询的数字x的大小有100000这么大，那么这个树状数组的节点个数就得有100001个这么多。

因为如果真的要在这里给大家讲清楚什么是树状数组的话，这篇文章得7000多字，所以如果希望了解树状数组这种数据结构了话，请移步我写的这篇文章扫清盲点：带你学习 树状数组 这种数据结构

• 在这道题中，因为题目给定范围是x <= 50000，这意味着输入的整数最大值为50000。而我们有50001个数据要处理。但是在树状数组中，我们需要将从1这个位置开始进行初始化，而数组呢，是从0开始的，所以我们要将我们所有输入的整数x去自增1，使其范围为1到50001。

• 这样，我们就需要用一个大小为50002的数组来容纳所有可能的值（包括下标为0的位置，虽然下标为0，这个位置不需要使用）

• lowbit(int x)：这是一个辅助函数，用于计算整数 x 的二进制表示中最低位的 1 所对应的数值。在 C++ 中，可以用 x & (-x) 快速计算 lowbit(x)。

• 在 track 方法中，我们需要保证更新过程不会超出数组的范围。因此，我们将条件设置为 x <= 50001，这样在更新过程中 x 的最大值为 50001，不会越界。
  当我们向树状数组中插入一个数 x 时，实际上需要更新多个数组元素。具体来说，我们首先将 x 自增 1（因为树状数组的下标从 1 开始），然后进入一个 while 循环，不断更新树状数组中的元素。每次更新后，我们都将 x 加上它的 lowbit(x)，直到 x 超过数组的最大下标（在这个例子中是 50001）。

• getRankOfNumber(int x)：这个函数用于计算小于等于 x 的值的个数。与 track 函数类似，我们首先对 x 执行自增操作（++x）。然后使用一个 while 循环进行前缀和查询。循环中，我们累加 v[x] 的值，并通过 x -= lowbit(x) 来更新 x。当 x 变为 0 时，循环结束，返回累加的结果。

具体的代码实现如下：

class StreamRank {int lowbit(int x){return x & (-x) ;}
public:vector<int> arrayTree;StreamRank(): arrayTree(50002,0) {}void track(int x) {++x; while(x <= 50001){++arrayTree[x];x = x + lowbit(x);}}int getRankOfNumber(int x) {++x;int ans = 0;while (x){ans += arrayTree[x];x -= lowbit(x);}return ans;}};

复杂度分析：

时间复杂度：

• track 方法：在这个方法中，我们更新树状数组。每次更新一个节点时，我们需要沿着树向上更新所有关联的父节点。由于树状数组的特性，这个过程的时间复杂度为 O(logN)，其中 N 是数组的大小。在本例中，N = 50002，所以时间复杂度为 O(log50002)。而我们可能调用track 方法n次，所以时间复杂度为 O(n * log50002)
• getRankOfNumber 方法：在这个方法中，我们从树状数组中查询累积和。与更新过程类似，查询过程也需要沿着树向上查询所有关联的父节点，时间复杂度同样为 O(logN)，即 O(log50002)。

空间复杂度：

• 由于我们使用了一个大小为 50002 的数组来存储树状数组，因此空间复杂度为 O(N)，即 O(50002)。

综上，这段代码的时间复杂度为 O(n * log50002)，空间复杂度为 O(50002)。

总结

这道题我给出了两种解决方法，它们各自有各自的优缺点。总的来说，这是一道不错的题目，难度适中。

• 如果大家觉得我这篇文章写的好的话，请关注我，给我个赞和收藏，您的支持，是我持续输出优质内容的无上动力！