首页 > 试题广场 >

维护x的秩

[编程题]维护x的秩
  • 热度指数：5002 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

已知一个数组A及它的大小n，在读入这串数的时候算出每个数的秩，即在当前数组中小于等于它的数的个数(不包括它自身)。从而返回一个int数组，元素为每次加入的数的秩。保证数组大小小于等于5000。

测试样例： 
[1,2,3,4,5,6,7],7
返回：[0,1,2,3,4,5,6]
算法知识视频讲解
开通博客
头像 一只老风铃
发表于 2021-06-24 13:52:56
要求随着数字的到来统计之前所有比当前小的数字的数目通过维护一棵二叉搜索树来实现，树的节点增加一个域Count用于统计左孩子节点的总数即：比当前节点更小的节点的数目 那么一个新的数字A[i]，从根节点开始插入如果大于某节点，那么其最终ans[i]+=count+1即：累加上某节点以及该节点所有左 展开全文
去ta的博客 赞 (1) 回复(1) 收起

问题信息

高级结构 查找 排序
难度：
46条回答 15343浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号