找出数字x的秩(小于或等于x的值的数目)
找出数字x的秩(小于或等于x的值的数目)
一贱书生 发表于12个月前
找出数字x的秩(小于或等于x的值的数目)
  • 发表于 12个月前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

/**

 * 功能:假设你正在读取一串整数。每隔一段时间,你希望能找出数字x的秩(小于或等于x的值的数目)。

 * 实现track(int x)方法,每读入一个数字就会调用该方法;以及getRankOfNumber( int x)方法,返回值为小于或等于x的元素个数(不包括x本身)。
 */



[java] view plain copy

 

  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

 

  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.       
共有 人打赏支持
粉丝 14
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: