邢台企业做网站费用,网站英文,沃尔玛跨境电商平台,网站建设的研发项目题目链接
数字流的秩
题目描述 注意点
x 50000
解答思路
可以使用二叉搜索树存储出现的次数以及数字的出现次数#xff0c;方便后续统计数字x的秩关键在于构建树的过程#xff0c;如果树中已经有值为x的节点#xff0c;需要将该节点对应的数字出现次数加1#xf…题目链接
数字流的秩
题目描述 注意点
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);*/关键点
构建二叉搜索树的过程
