找出数字x的秩（小于或等于x的值的数目）

淩亂°似流年 2022-01-13 14:13 164阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

/\*\*

\* 功能：假设你正在读取一串整数。每隔一段时间，你希望能找出数字x的秩（小于或等于x的值的数目）。

\* 实现track(int x)方法，每读入一个数字就会调用该方法；以及getRankOfNumber( int x)方法，返回值为小于或等于x的元素个数（不包括x本身）。  
\*/  
  
  
**\[java\]** [view plain][] [copy][view plain]

1.  /\*\*
2.  \* 思路：采用二叉查找树
3.  \* 执行中序遍历，并在访问结点时利用计数器记录数量，找到x时，计数器变量将会是小于x的元素的数量。
4.  \* 在查找期间，如果向左移动，计数器不会变，因为右边跳过的所有指都比x大。
5.  \* 向右移动时，跳过了左边的一堆元素，因此必须增加计数器的值，这个值等于左子树的元素个数。
6.  \*/
7.  private static RankNode root=null;
8.  public static void track(int number)\{
9.  if(root==null)
10. root=new RankNode(number);
11. else
12. root.insert(number);
13. \}
14. 
15. public static int getRankOfNumber(int number)\{
16. return root.getRank(number);
17. \}

**\[java\]** [view plain][] [copy][view plain]

1.  class RankNode\{
2.  int leftSize=0;
3.  RankNode left,right;
4.  int data=0;
5.  public RankNode(int d)\{
6.  this.data=d;
7.  \}
8.  
9.  public void insert(int d)\{
10. if(d<=data)\{
11. if(this.left==null)
12. left=new RankNode(d);
13. else
14. left.insert(d);
15. \}else\{
16. if(this.right==null)
17. right=new RankNode(d);
18. else
19. right.insert(d);
20. \}
21. \}
22. 
23. public int getRank(int d)\{
24. if(d==this.data)
25. return this.leftSize;
26. else if(d<this.data)\{
27. if(left==null)
28. return -1;
29. else
30. return left.getRank(d);
31. \}else\{
32. if(right==null)
33. return -1;
34. else
35. return this.leftSize+1+right.getRank(d);
36. \}
37. \}
38. 
39. \}

转载于:https://my.oschina.net/u/2822116/blog/793329

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/00560cac267d441daa8352c1c275c35b.png
[view plain]: http://blog.csdn.net/shangqing1123/article/details/47946243#