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.
关注 九章算法
微信扫一扫关注公众号