Lintcode249 Count of Smaller Number before itself solution 题解
发布在Lintcode题解2018年2月22日view:627HTML5YiksiAssowcss3XmgvzgrkIgoriAssowES6BrettBat移动开发MVVM性能优化ReactES6Thrift独立开发者Hexonpm混合应用开发微信小程序极乐科技小程序商店支付宝小程序权限控制RESTful博客expressangularjs日志
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】 Give you an integer array (index from 0 to n-1, where n is the size of this array, data value from 0 to 10000) . For each element Ai in the array, count the number of element before this element Ai is smaller than it and return count number array.

Notice:We suggest you finish problem Segment Tree Build,Segment Tree Query II and Count of Smaller Number first.

给定一个整数数组(下标由 0 到 n-1, n 表示数组的规模,取值范围由 0 到10000)。对于数组中的每个ai元素,请计算ai前的数中比它小的元素的数量。

【注】:做此题前最好先完成 Segment Tree Build,Segment Tree Query IICount of Smaller Number

【题目链接】

www.lintcode.com/en/problem/count-of-smaller-number-before-itself/

【题目解析】

此题可用线段树来做。

首先以0-10000为区间建树,并将所有区间count设为0。每一个最小区间(即叶节点)的count代表到目前为止遇到的该数的数量。

然后开始遍历数组,遇到A[i]时,去查0-A[i]-1区间的count,即为比A[i]小的数的数量

查完后将A[i]区间的count加1即可

【参考答案】

www.jiuzhang.com/solutions/count-of-smaller-number-before-itself/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN

我的收藏