当前位置：首页 > news >正文

LeetCode -- Count of Smaller Numbers After Self

news 来源：原创 2024/5/9 22:44:24

题目描述：

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].

给定一个数组a[n]，返回数组b[n]，每个元素对应当前元素a[i]右边小于a[i]的个数。

思路：
本题比较直接的实现是创建二叉搜索树。

从右向左遍历数组a[n]，i∈[n-1,0]，创建二叉树。
二叉树的每个节点node存放a[i]以及小于当前节点的元素个数。
如果a[i]小于node.Value，node.Count++，向左走；走不动时把a[i]创建为叶子；
如果a[i]大于等于node.Value,当前count++，向右走；走不动时把a[i]创建为叶子
返回当前count作为结果。

实现代码：

public class Solution {
    public IList<int> CountSmaller(int[] nums) 
    {
        if (nums == null || nums.Length == 0){
    		return new List<int>();
    	}
    	
    	var result = new List<int>(){0 /*there is no value on the right of last number*/};
    	var len = nums.Length;
    	var root = new BTNode(nums[len - 1]);
    	for (var i = len - 2; i >= 0; i--){
    		// add the value of arr on the tree one by one
    		// also update the count of smaller on the 'root' node
    		var smallerCount = BuildAndCount(root, nums[i]);
    		result.Add(smallerCount);
    	}
    	
    	result.Reverse();
    	
    	return result;
     }
     
     public int BuildAndCount(BTNode current, int value){
    
     	int countOfSmaller = 0;
     	while(true){
    		if(value > current.Value){
    			
    			// value bigger than current node , add current node's 'count of smaller' on this value
    			countOfSmaller += current.Count + 1;
    			// keep going right ,until reach leaf
    			if(current.Right == null){
    				current.Right = new BTNode(value);
    				break;
    			}else{
    				current = current.Right;
    			}
    		}
    		else{
    			// value is smaller than current node value , increase the count of smaller on current node
    			current.Count ++;
    			// put value on left tree leaf
    			if(current.Left == null){
    				current.Left = new BTNode(value);
    				break;
    			}
    			else{
    				current = current.Left;
    			}
    		}
    	}
    	
    	return countOfSmaller;
     }
     
     public class BTNode{
     	public BTNode Left;
    	public BTNode Right;
    	public int Value;
    	public int Count ;
    	public BTNode (int v){
    		Value = v;
    		Count = 0;
    	}
     }
}

也可以考虑BIT的实现：
https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/