数字流的秩

题目链接

数字流的秩

题目描述

注意点

  • x <= 50000

解答思路

  • 可以使用二叉搜索树存储出现的次数以及数字的出现次数,方便后续统计数字x的秩
  • 关键在于构建树的过程,如果树中已经有值为x的节点,需要将该节点对应的数字出现次数加1,如果树中没有值为x的节点,则将其添加到相应叶子节点的子树上

代码

class StreamRank {
    TreeNode root;

    public StreamRank() {
        root = null;
    }
    
    public void track(int x) {
        if (root == null) {
            root = new TreeNode();
            root.val = x;
            root.num = 1;
            return;
        }
        // 找到值为x的节点,没找到x则需要找到x应该插入的节点位置
        TreeNode node = findX(x, root);
        // 找到了值为x的节点
        if (node.val == x) {
            node.num += 1;
            return;
        }
        // 没有找到需要将值为x的新节点插入到树中
        TreeNode newNode = new TreeNode();
        newNode.val = x;
        newNode.num = 1;
        if (node.val > x) {
            node.left = newNode;
        } else {
            node.right = newNode;
        }
    }
    
    public int getRankOfNumber(int x) {
        return countNumber(x, root);
    }

    public TreeNode findX(int x, TreeNode node) {
        if (node.val == x) {
            return node;
        }
        if (node.val > x) {
            if (node.left == null) {
                return node;
            }
            return findX(x, node.left);
        } else {
            if (node.right == null) {
                return node;
            }
            return findX(x, node.right);
        }
    }

    public int countNumber(int x, TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 左子树更有可能小于等于x
        int sum = countNumber(x, node.left);
        if (node.val <= x) {
            sum = sum + node.num + countNumber(x, node.right);
        }
        return sum;
    }
}

class TreeNode {
    TreeNode left;
    TreeNode right;
    int val;
    int num;
}

/**
 * Your StreamRank object will be instantiated and called as such:
 * StreamRank obj = new StreamRank();
 * obj.track(x);
 * int param_2 = obj.getRankOfNumber(x);
 */

关键点

  • 构建二叉搜索树的过程

相关推荐

  1. 矩阵公式小结

    2024-07-10 22:06:04       39 阅读
  2. 核和值域关系:什么是矩阵

    2024-07-10 22:06:04       27 阅读
  3. 高等代数复习:矩阵基本公式

    2024-07-10 22:06:04       20 阅读
  4. 高等代数复习:矩阵分解

    2024-07-10 22:06:04       21 阅读
  5. QuanTA: 一种新高效微调范式

    2024-07-10 22:06:04       14 阅读
  6. 295. 数据中位数

    2024-07-10 22:06:04       17 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-10 22:06:04       3 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-10 22:06:04       3 阅读
  3. 在Django里面运行非项目文件

    2024-07-10 22:06:04       2 阅读
  4. Python语言-面向对象

    2024-07-10 22:06:04       2 阅读

热门阅读

  1. 深入理解UTF-8 Encoding在C#中的应用与异常处理

    2024-07-10 22:06:04       10 阅读
  2. Linux 常用命令 - mkdir【创建新目录】

    2024-07-10 22:06:04       10 阅读
  3. stm32实现IIC读写

    2024-07-10 22:06:04       7 阅读
  4. 中小企业和数智化的距离,只差一块华为IdeaHub

    2024-07-10 22:06:04       11 阅读
  5. C# —— Directory类

    2024-07-10 22:06:04       7 阅读
  6. 在Ubuntu 22.04上安装Docker最新版本

    2024-07-10 22:06:04       8 阅读