You are given an integer array nums and you have to return a new counts array. The counts array has the property wherecounts[i]
is the number of smaller elements to the right of nums[i]
.
Example:
[leetcode 315] Count of Smaller Numbers After Self
之前做笔试题的时候见到过这道题,我的解法就是最直接的,对每一个元素,每次遍历它后面的元素,找到比它小的元素个数,然后超时了,显然这种最直接的方法对于笔试是应该摒弃的。。。
下面给出discuss上的两种解法,分别使用二叉搜索树和归并排序实现,特别的好。
二叉搜索树
这个是排名第一的答案,遍历给定数组的过程就是建立一棵二叉搜索树的过程,一个节点有这么几个属性:左右节点,节点值,节点值相同的元素个数,节点左子树的个数。
对当前遍历的元素(从后往前),如下插入:从根节点出发,如果小于根节点,就直接转到根节点的左子树,如果等于根节点,将根节点的相同元素个数++,该元素对应的count[i]
为节点左子树个数加先前的元素个数,如果大于,转到根节点右子树,并将节点的左子树的个数传入。代码如下:
归并排序
这个比较好理解,只要知道归并排序的思想,然后在排序的过程中,记录右边小于左边的个数,并叠加到左边,右边不变,代码如下:
这里我还是举个例子吧(交换值而不是代码中所示的交换索引),比如[5,2,6,1]
,分解后变为5
,2
,6
,1
,然后是5和2归并,第一个位置,2小于5,那么将count++,但是2对应的count[1]=0
不变,第二个位置,将5添加,并将5对应的count[0]
和count相加赋给count[0],count[0]=1
,同理对于6和1,count[2]=1,count[3]=0
;然后继续归并,2,5
和1,6
,第一个位置是1,count=1,第二个位置是2,count[1]=count[1]+count=1
,第三个位置是5,count[0]=count[0]+count=2
,第4个位置是6,count[2]=count[2]
,归并完成,这样对应的count数组就是:[2,1,1,0]
。