LeetCode Count of Smaller Numbers After Self

原题链接在这里：https://leetcode.com/problems/count-of-smaller-numbers-after-self/

题目：

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].

题解：

从右向左扫描数组nums, try to find the position of nums[i] in BST.

For each BST node, it contains its left subtree size count, its duplicate count.

When inserting a new node, returns the sum of smaller count.

Time Complexity: O(n^2). BST不一定balance. Space: O(n).

AC Java:

 class Solution {

     public List<Integer> countSmaller(int[] nums) {

         LinkedList<Integer> res = new LinkedList<>();

         if(nums == null || nums.length == 0){

             return res;

         }

         int n = nums.length;

         res.offerFirst(0);

         TreeNode root = new TreeNode(nums[n - 1]);

         root.count = 1;

         for(int i = n - 2; i >= 0; i--){

             int smallerCount = insert(root, nums[i]);

             res.offerFirst(smallerCount);

         }

         return res;

     }

     private int insert(TreeNode root, int num){

         int smallerCountSum = 0;

         while(root.val != num){

             if(root.val > num){

                 root.leftCount++;

                 if(root.left == null){

                     root.left = new TreeNode(num);

                 }

                 root = root.left;

             }else{

                 smallerCountSum += root.leftCount + root.count;

                 if(root.right == null){

                     root.right = new TreeNode(num);

                 }

                 root = root.right;

             }

         }

         root.count++;

         return smallerCountSum + root.leftCount;

     }

 }

 class TreeNode{

     int val;

     int count;

     int leftCount;

     TreeNode left;

     TreeNode right;

     public TreeNode(int val){

         this.val = val;

         this.count = 0;

         this.leftCount = 0;

     }

 }

类似Reverse Pairs.

巴特西

LeetCode Count of Smaller Numbers After Self

最新文章

热门文章