数字流的秩

题目链接

数字流的秩

题目描述

注意点

• 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;}// 左子树更有可能小于等于xint 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);*/

关键点

• 构建二叉搜索树的过程