文档章节

找出数字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
python测试开发学习笔记

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

知止内明
2017/12/21
0
0
查找----基于二叉查找树

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

Superheros
2017/12/16
9
0
数组中第K大的元素

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

王大豆
2015/09/05
265
0
SQL中的取整函数、取小数

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

AlunE
01/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

docker多容器部署lnmp环境

环境:RHEL7.5 ip:192.168.10.102,主机名:lb02 一、创建web、数据库目录 web网站目录为:/wwwroot,属主属组:www [root@lb02 ~]# mkdir /wwwroot[root@lb02 ~]# useradd -s /sbin/nolo...

人在艹木中
14分钟前
0
0
eclipse运行springboot项目报错‘找不到或无法加载主类’

这是一个很烦躁的问题~,往往困住大家好长时间,然后各种百度。借此,咱将这个问题有可能产生的原因进行一下总结。若有不完善之处欢迎大家在下面留言指出~~ Duang!问题出现 然后开始尝试解决...

Code辉
35分钟前
0
0
springboot oauth2 跨域设置

@Overridepublic void configure(HttpSecurity http) throws Exception { http .authorizeRequests() .antMatchers("/security/**") .authentica......

昆虫大侠
36分钟前
0
0
08-利用思维导图梳理JavaSE-泛型

08-利用思维导图梳理JavaSE-泛型 主要内容 1.泛型的基本概念 1.1.定义 1.2.使用前提 1.3.使用泛型的好处 2.泛型的使用 2.1.泛型类定义 2.2.泛型对象定义 2.3.泛型中的构造方法 2.4.泛型方法的...

飞鱼说编程
38分钟前
0
0
Docker 部署 Spring Boot 项目指南

仅想在Docker里运行一个Spring Boot项目,捣鼓了许久。。。 本文主要适用于Windows环境下的Docker 一、运行环境 Windows 10 Maven 3.5 Docker 18.06.1-ce-win73 (19507) 二、创建Spring Boot...

AmosWang
44分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部