文档章节

找出数字x的秩(小于或等于x的值的数目)

一贱书生
 一贱书生
发布于 2016/11/24 08:55
字数 349
阅读 2
收藏 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.       

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
Python学习之day2运算符

一、Python模块库分类 python模块库主要分两类,一类是官方标准库,另一类是三方库。官方标准库不需要用户自己进行 特殊安装即可使用,三方库类似插件需要用户去下载对应的三方库方可使用。 ...

demonlg
2017/10/18
0
0
查找----基于二叉查找树

上一篇:基于有序数组的查找 参照数据结构--符号表API实现。 首先,定义二叉树结点类: 其中N为以该节点为根的子树的节点总数,计算方法如下: size(x) = size(x.left) + size(x.right) + 1...

Superheros
2017/12/16
9
0
python测试开发学习笔记

练习题1:请大家找出s="aabbccddxxxxffff"中,字母出现次数最多的字母 算法1: 遍历所有的字符,把每一个字符出现的次数, 用count函数做一个统计,声明一个存储最大值的字典对象, 遍历的时...

知止内明
2017/12/21
0
0
SQL中的取整函数、取小数

取整函数: 1、trunc(value,precision)按精度(precision)截取某个数字,不进行舍入操作。 返回截尾到y位小数的x值:trunc(x,[y]): 2、round(value,precision)根据给定的精度(precision)输入...

AlunE
2018/01/15
0
0
数组中第K大的元素

数组中第K大的元素总结 解法1: 我们可以对这个乱序数组按照从大到小先行排序,然后取出前k大,总的时间复杂度为O(nlogn + k)。 解法2: 如果k很小,比如第五个最大的数,而整个数组的长度非...

王大豆
2015/09/05
265
0

没有更多内容

加载失败,请刷新页面

加载更多

刚入职阿里,告诉你真实的职场生活,兼谈P6、P7、P8的等级

一:拿下offer的人,基本上都有什么特征? 二:为什么选择阿里? 三:阿里的工作氛围什么样? 四:阿里的薪资情况? 五:阿里的晋升空间有多大? 最近部门招聘,很多工程师,包括我在内都参与...

java知识分子
16分钟前
2
0

中国龙-扬科
19分钟前
1
0
深入理解定时器系列第一篇——理解setTimeout和setInterval

很长时间以来,定时器一直是javascript动画的核心技术。但是,关于定时器,人们通常只了解如何使用setTimeout()和setInterval(),对它们的内在运行机制并不理解,对于与预想不同的实际运行状...

Jack088
22分钟前
2
0
windows 安装nvm

1、nvw-windows的官网:https://github.com/coreybutler/nvm-windows/releases 2、选择nvm-setup.zip安装 3、配置环境变量 4、检查nvm是否安装成功 使用管理员权限打开一个命令行。输入nvm v...

灰白发
33分钟前
1
0
MySQL

慢日志查询作用 慢日志查询的主要功能就是,记录sql语句中超过设定的时间阈值的查询语句。例如,一条查询sql语句,我们设置的阈值为1s,当这条查询语句的执行时间超过了1s,则将被写入到慢查...

士兵7
34分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部