题目链接
数字流的秩
题目描述
注意点
解答思路
- 可以使用二叉搜索树存储出现的次数以及数字的出现次数,方便后续统计数字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;
}
TreeNode node = findX(x, root);
if (node.val == x) {
node.num += 1;
return;
}
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;
}
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;
}
关键点