文档章节

找出数字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
Python3 欧拉计划 问题31-35

问题26—30参见:https://www.jianshu.com/p/756fa99c2b03 31、硬币组合 英国的货币单位包括英镑£和便士p,在流通中的硬币一共有八种: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p...

AiFan
2017/12/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

移动端Appium自动化测试框架的优势

众所周知,现在市面上的移动端操作系统已被Android和IOS占领,其中Android的份额更是在80%以上。那么面对市面上林林总总的自动化测试框架和工具,为什么说Appium在自动化测试框架的统治级优势...

程序猿拿Q
7分钟前
0
0
设计模式 之 观察者模式

设计模式 之 观察者模式 场景 场景比较简单,当一个对象的状态发生改变时,自动通知所有依赖(或观察)它的对象。 比如:发布/订阅 原理:发布者存储N个订阅者的对象信息,当发布者发布消息时...

GMarshal
11分钟前
0
0
linux 常用

netstat -tunlp |grep 8080 查看8080 占用 netstat -tunlp 用于查看所有的端口号的进程情况

west_coast
16分钟前
1
0
Bytom信息上链教程

比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom 很多了解比原链的都知道,比原链是专注信息和数字资产在链上交互和流转的...

比原链Bytom
21分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部