欢迎您的访问
专注架构,Java,数据结构算法,Python技术分享

计算右侧小于当前元素的个数

计算右侧小于当前元素的个数

100_1.png

解题思路

1、 暴力算法,两层for循环嵌套, O(n^2) 最后测试会超时,需要优化。
2、 方法1:使用 BST(二叉搜索/排序数)

BST(二叉搜索/排序数) Java代码

class Solution {
    // 采用二叉搜索的做法,在树节点除了有val值外,还有个count值,用于记录它的左子树上有多少个节点
    // 这样,最开始那个点形成的树节点,count值是0
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<>();
 if (nums == null || nums.length <= 0) return list; int[] ret = new int[nums.length]; TreeNode root = null; for (int i = nums.length - 1; i >= 0; i--) { root = insert(root, new TreeNode(nums[i]), ret, i); } for (int n : ret) { list.add(n); } return list; } /** * 插入到树里面的时候,还需要更小count域的值。 * @param root 根节点 * @param node 待插入的节点 * @param ret 当node插入到树之后,实际上它的ret已经是确定的来 * @param i 数组下标 */ public TreeNode insert(TreeNode root, TreeNode node, int[] ret, int i) { if (root == null) { root = node; return root; } // 如果待插入的数比较小,或者相等的时候,就往左子数中插入,且根节点的count加1 if(node.val <= root.val) { root.count++; root.left = insert(root.left, node, ret, i); } else { // 对应点的count增加越过的那个节点的count值 + 1。因为越过的那个节点也比它小 ret[i] += root.count + 1; root.right = insert(root.right, node, ret, i); } return root; } // 树节点中除了val,还有个count,来统计它的左子树的节点 class TreeNode { int val; int count; TreeNode left; TreeNode right; public TreeNode(int value) { this.val = value; this.count = 0; this.left = null; this.right = null; } } } 
赞(0) 打赏
版权归原创作者所有,任何形式转载请联系作者;码农code之路 博客站点 » 计算右侧小于当前元素的个数

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏