英文网站建设60,软件开发和网站建设那个好,图片设计与制作软件下载,深圳人才市场招聘网最新招聘信息题目描述 假设你正在读取一串整数。每隔一段时间#xff0c;你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作#xff0c;也就是说#xff1a; 实现 track(int x) 方法#xff0c;每读入一个数字都会调用该方法#xff1b; 实现 g…题目描述 假设你正在读取一串整数。每隔一段时间你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作也就是说 实现 track(int x) 方法每读入一个数字都会调用该方法 实现 getRankOfNumber(int x) 方法返回小于或等于 x 的值的个数。
注意本题相对原题稍作改动
示例:
输入:
[StreamRank, getRankOfNumber, track, getRankOfNumber]
[[], [1], [0], [0]]
输出:
[null,0,null,1]提示
x 50000track 和 getRankOfNumber 方法的调用次数均不超过 2000 次
解题思路与代码
这道题其实有一种特别简单的做法和一个需要你有一定知识储备的做法前者是我自己想出来的时间复杂度偏高但是空间复杂度比较低。后者呢时间复杂度偏低但是空间复杂度缺偏高可以说各有优点吧。
对于后者用到了一种叫做树状数组的数据结构你也可以理解为一种算法的思想或者技巧。掌握这种数据结构的过程可能比较难你首先得知道树状数组是个什么东西才能知道里面的操作为什么这么去做。
那我们就一步一步的来教会大家如何用这两种方法来解决这道题
方法1使用sort函数帮助我们排序。 顾名思义我们用一个vector数组来帮助我们去存储数据。 每次读取一个数字我们就把这个数据添加到数组的最后面然后对整个数组进行排序用sort函数排序 这样track方法就编写完成啦。 紧接着我们来编写一下getRankOfNumber方法其实这个方法的实现也很简单。因为我们已经把读到的所有元素进行排序了这个时候只需要从后往前去遍历整个数组找到第一个小于等于x的元素返回这个元素的下标 1就行了。如果找不到这样的元素那就返回0就好啦。两个方法其实都不难的
具体的代码如下
class StreamRank {
public:vectorint 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:vectorint 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)。
总结
这道题我给出了两种解决方法它们各自有各自的优缺点。总的来说这是一道不错的题目难度适中。
如果大家觉得我这篇文章写的好的话请关注我给我个赞和收藏您的支持是我持续输出优质内容的无上动力
