首页 > 代码库 > 11.8 实现数据结构和算法支持track和rank操作。
11.8 实现数据结构和算法支持track和rank操作。
track操作类似与插入操作。
rank操作返回比当前元素小或者相等的元素数。
思路：track操作插入构造BST（没有保证平衡），但是节点增加一个leftSize，这里学习一下。
public class Solution { private static RankNode root = null; public static void track(int number) { if (root == null) { root = new RankNode(number); } else { root.insert(number); } } public static int getRankOfNumber(int number) { return root.getRank(number); } public static void main(String[] args) { track(20); track(15); track(25); track(10); track(23); track(5); track(13); track(24); System.out.println(getRankOfNumber(20)); System.out.println(getRankOfNumber(15)); System.out.println(getRankOfNumber(8)); }}class RankNode { int val; int leftSize; RankNode left; RankNode right; public RankNode(int v) { val = v; } public void insert(int t) { if (t <= val) { if (left != null) { left.insert(t); } else { left = new RankNode(t); } leftSize++; } else { if (right != null) { right.insert(t); } else { right = new RankNode(t); } } } public int getRank(int t) { if (t == val) { return leftSize; } else if (t < val) { if (left == null) return -1; else return left.getRank(t); } else { if (right == null) return -1; else { return right.getRank(t) + leftSize + 1; } } }}
11.8 实现数据结构和算法支持track和rank操作。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。