Problem
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:
Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
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.
class Solution { public ListcountSmaller(int[] nums) { List res = new ArrayList<>(); if (nums == null || nums.length == 0) return res; int len = nums.length; TreeNode root = new TreeNode(nums[len-1]); res.add(0); for (int i = len-2; i >= 0; i--) { int count = insertNode(root, nums[i]); res.add(count); } Collections.reverse(res); return res; } private int insertNode(TreeNode root, int num) { int count = 0; //the # of smaller numbers of num while (root != null) { if (num <= root.val) { root.count++; if (root.left == null) { root.left = new TreeNode(num); break; } else root = root.left; } else { count += root.count; if (root.right == null) { root.right = new TreeNode(num); break; } else root = root.right; } } return count; } } class TreeNode { int val; int count = 1; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/72506.html
摘要:当我们希望查询时,则从根节点开始寻找其所在的区间,如果位于左侧区间,则查询左子树啊,如果位于右侧区间,则查询右子树。如果横跨了分割点,则分别查询左子树的部分和右子树的部分。 题目要求 You are given an integer array nums and you have to return a new counts array. The counts array has t...
摘要:复杂度思路每遍历到一个数,就把他到已有的中。对于每一个,维护一个和一个自身的数目。比如,然后每次遍历到一个数,就把对应位置的值加一。比如碰到之后,就变成,然后统计的和。 Leetcode[315] Count of Smaller Numbers After Self ou are given an integer array nums and you have to return a...
摘要:我们建立的,其中解决重复值的问题,记录左子树的节点数。给定要找的点,这里的规律就是,往右下走,说明当前点和当前的的左子树的值全部比小。我们走到要向右,这是左子树没变化,这里也不变。 题目细节描述参看leetcode。 今天的重头戏 LC315 Count of Smaller Numbers After Self.在讲这个题目之前,请思考这个问题。在BST找到所有比Node P小的节点...
摘要:题目链接的题,用来做,这种求有多少的题一般都是。里多加一个信息表示以为的节点数。也可以做,因为是统计有多少的,其实就是求从最小值到的。的是,要做一个映射,把的值映射到之间。所以先把给一下,用一个来做映射。还有的方法,参考 315. Count of Smaller Numbers After Self 题目链接:https://leetcode.com/problems... divi...
摘要:题目意思就是要一个个的返回当前的最小值。所以解法自然就是。我们需要找出被打乱的点并返回正确结果。然后将两个不正确的点记录下来,最后回原来正确的值。如果是叶子节点,或者只有一个子树。思想来自于的代码实现。 跳过总结请点这里:https://segmentfault.com/a/11... BST最明显的特点就是root.left.val < root.val < root.right.v...
阅读 2079·2023-04-26 00:50
阅读 2464·2021-10-13 09:39
阅读 2178·2021-09-22 15:34
阅读 1583·2021-09-04 16:41
阅读 1321·2019-08-30 15:55
阅读 2414·2019-08-30 15:53
阅读 1665·2019-08-30 15:52
阅读 726·2019-08-29 16:19