热门标签
热门文章
- 1SE-ResNet的实现
- 2为什么这么多半导体公司都重视大学计划？_公司 大学计划
- 3vue-router中query取值的坑_route.query 取值类型
- 4LLM 模型融合实践指南：低成本构建高性能语言模型_dare llm 模型融合
- 5计算机网络期中复习提纲-酷酷的聪整理版（南邮/通达）_计网期中考试
- 6idea/jrebel/dataGrip激活_datagrip学生认证激活 csdn
- 7【Jetpack篇】Paging的新增与删除_paging3 增删改
- 8android 时区查询表_android 时区列表
- 9SpringBoot项目连接MySQL数据库_mysql pom
- 10element-UI展开行expand动态加载数据时遇到的坑-展开多行数据相同
当前位置: article > 正文
《python算法与数据结构2000讲》0315. 计算右侧小于当前元素的个数
作者：羊村懒王 | 2024-03-13 03:48:04
赞
踩
《python算法与数据结构2000讲》0315. 计算右侧小于当前元素的个数
《python算法与数据结构2000讲》0315. 计算右侧小于当前元素的个数
- 标签：树状数组、线段树、数组、二分查找、分治、有序集合、归并排序
- 难度：困难
题目大意
给定一个整数数组 nums 。
要求：返回一个新数组 counts 。其中 counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
解题思路
可以用树状数组解决。
首先对数组进行离散化处理。把原始数组中的数据映射到 [0, len(nums) - 1] 这个区间。
- 然后逆序顺序从数组
nums中遍历元素nums[i]。计算其离散化后的排名index，查询比index小的数有多少个。将其记录到答案数组的对应位置ans[i]上。 - 然后在树状数组下标为
index的位置上，更新值为1。
重复上述步骤直到遍历完所有元素。最后输出答案数组即可。
代码
推荐阅读
相关标签
