Google 2016 面试题6 Count of Smaller Numbers After Self(数组计数)
Google2016面试题，附答案和参考代码。...
(点击上方关注九章算法，获取最新IT求职干货！)
题目描述给定一个数组nums,返回一个计数数组count，count表示nums中第i个右边有多少个数小于nums
Example:
nums = [5, 2, 6, 1]
输出[2,1,1,0]
分析解答
此题不难给出O(N^2)的算法，先穷举nums中每个位置i，再穷举右边的数计算有多少个小于nums。难点在于利用数据结构进行优化从而降低时间复杂度。线段树（segment tree）和平衡树（Balanced Binary Tree）是两种可以使用的数据结构。
线段树的每个节点表示一段区间，记录这个区间的某些信息，其基本思想是把区间一分为二，二分为四。。。直到不可再分（因此叶子节点的区间只包含一个数），如此可以把任意区间表示成log（区间大小）个子区间的拼接，以降低查询时间复杂度。在本题中，假设nums中的数字范围在0到maxnum之间，那么建树的区间为[0,maxnum]（也就是根节点所表示的区间）。每个节点记录其表示区间内的数字个数。本题涉及两种线段树基本操作：插入和查询。插入操作把nums插入到线段树相应位置，同时对所有经过的区间的sum值进行累加；查询操作需要查询区间[0,nums-1]所包含的数字个数，利用已经建好的线段树把查询区间分割为若干个节点所表示的区间，统计并返回这些节点的sum值之和。
平衡树用途更广，代码复杂度也更高，是一种保持叶子节点深度平衡的二叉搜索树，有多种方法实现，因篇幅有限不再赘述，大家可以自行在网上搜索学习。
参考程序
更多算法面试题答案：http://www.jiuzhang.com/solutions/
面试官角度分析
可以先答出O(n^2)的时间复杂度然后面试官沟通后给出小于O(N^2)的算法比如线段树解决的方法可以达到hire的程度。
相关练习题
http://www.lintcode.com/problem/segment-tree-build
http://www.lintcode.com/problem/segment-tree-query
http://www.lintcode.com/problem/segment-tree-modify
http://www.lintcode.com/problem/interval-minimum-number
Google 2016 面试题5 | 岛屿计数2
Google 2016 面试题4 | 矩阵中的最长上升路径
Google 2016 面试题3 | 摆动排序 II
Google 2016 面试题2 | 不构造树的情况下验证先序遍历
Google 2016 面试题1 | 数组补丁
关注公众号，回复类别关键字查看相关类别面试题集锦。关键字列表：动态规划，堆，哈希表，数组，二叉树，二分法，智力题，排序，概率，等等；
简介
九章算法,帮助更多中国人找到好工作!
九章算法，团队成员均为硅谷和国内顶尖IT企业工程师。提供算法培训、面试咨询、求职内推。目前开设课程有九章算法班、系统设计班、Java入门与基础算法班、九章算法强化班。更有android/big data/ios 等即将开课。
目前培训的程序员遍布中国、美国、加拿大、澳大利亚、英国、新加坡等14个国家和地区。
更多详情，登录www.jiuzhang.com，或致信info@jiuzhang.com.
关注 九章算法
微信扫一扫关注公众号
