Google 2016 面试题6 | Count of Smaller Numbers After Self(数组计数)

Google 2016 面试题6 | Count of Smaller Numbers After Self(数组计数)

Google 2016 面试题6 | Count of Smaller Numbers After Self(数组计数)

题目描述

给定一个数组nums,返回一个计数数组count，count[i]表示nums中第i个右边有多少个数小于nums[i]

Example:nums = [5, 2, 6, 1] 输出[2,1,1,0]

分析解答

此题不难给出O(N^2)的算法，先穷举nums中每个位置i，再穷举右边的数计算有多少个小于nums[i]。难点在于利用数据结构进行优化从而降低时间复杂度。线段树（segment tree）和平衡树（Balanced Binary Tree）是两种可以使用的数据结构。

线段树的每个节点表示一段区间，记录这个区间的某些信息，其基本思想是把区间一分为二，二分为四。。。直到不可再分（因此叶子节点的区间只包含一个数），如此可以把任意区间表示成log（区间大小）个子区间的拼接，以降低查询时间复杂度。在本题中，假设nums中的数字范围在0到maxnum之间，那么建树的区间为[0,maxnum]（也就是根节点所表示的区间）。每个节点记录其表示区间内的数字个数。本题涉及两种线段树基本操作：插入和查询。插入操作把nums[i]插入到线段树相应位置，同时对所有经过的区间的sum值进行累加；查询操作需要查询区间[0,nums[i]-1]所包含的数字个数，利用已经建好的线段树把查询区间分割为若干个节点所表示的区间，统计并返回这些节点的sum值之和。

平衡树用途更广，代码复杂度也更高，是一种保持叶子节点深度平衡的二叉搜索树，有多种方法实现，大家可以自行在网上搜索学习。

参考程序：

public class Solution{ class SegmentTreeNode{ public int start,end; public int count; public SegmentTreeNode left,right; public SegmentTreeNode(int short,int end,int count){ this.start =start; this.end =end; this.count =count; this.left =this.right =null; }}SegmentTreeNode root;public SegmentTreeNode build(int start,int end){ if(start>end){ return null; } SegmentTreeNode root =new SegmentTreeNode(start,end,0); if(start!=end){ int mid =(start+end)/2; root.left =build(start,mid); root.right =build(mid+1,end); } else{ root.count =0; } return root;}public int querySegmentTree(SegmentTreeNode root,int start,int end){ if(start==root.start&&root.end==end){ return root.count; } int mid =(count.start+root.end)/2; int leftcount =0,rightcount =0 //左子区 if(start<=mid){ if(mid countOfSmallerNumberII(int []A){ root =build(0,10000); ArrayListans =new ArrayList(); int res; for(int i=0;i0){ res=querySegmentTree(root,0,A[i]-1); } modifySegmeniTree(root,A[i],1); ans.add(res); } return ans; }}

面试官角度分析

可以先答出O(n^2)的时间复杂度然后面试官沟通后给出小于O(N^2)的算法比如线段树解决的方法可以达到hire的程度。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。