文档章节

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

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

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 723
码字总数 600072
作品 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
数学基础(二)——参数估计与矩阵运算基础

参数估计与矩阵运算基础 ps: 个人笔记 根据视频和PDF学习 1 期望 离散型: 连续型: 即:概率加权下的“平均值” 期望的性质 无条件成立 若X和Y相互独立 反之不成立。事实上,若E(XY)=E(X)E...

qq_41010142
04/16
0
0
位运算实用方法

1、一些应用技巧 (1) 判断int型变量a是奇数还是偶数 a&1 = 0 偶数 a&1 = 1 奇数 (2) 取int型变量a的第k位 (k=0,1,2……sizeof(int)),即a>>k&1 (3) 将int型变量a的第k位清0,即a=a&~(1<<k) (...

daniel-john
03/05
5
0
Math.ceil(),Math.floor()与Math.round()三个函数的定义。

JavaScript: The Definitive Guide, 4th Edition中对Math.ceil(),Math.floor()与Math.round()三个函数的定义。 Math.ceil() ceil() 方法可对一个数进行上舍入。 参数必须是一个数值。返回值大...

林文聪
2012/09/25
0
0
Lintcode3 Digit Counts solution 题解

【题目描述】 Count the number of k's between 0 and n. k can be 0 - 9. 计算数字k在0到n中的出现的次数,k可能是0~9的一个值。 【题目链接】 http://www.lintcode.com/en/problem/digit-c...

coderer
2017/04/09
0
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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

pbgo: 基于Protobuf的迷你RPC/REST框架

https://www.oschina.net/p/pbgo

chai2010
20分钟前
0
0
rsync工具介绍、常用选项以及通过ssh同步

linux下的文件同步工具 rsync rsync是非常实用的一个同步工具,可以从a机器到b机器传输一个文件,也可以备份数据,系统默认没有这个工具,要使用命令 yum install -y rsync 安装。 rsync的命...

黄昏残影
35分钟前
0
0
OSChina 周四乱弹 —— 表妹要嫁人 舅妈叮嘱……

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @哈哈哈哈哈嗝:一定要听——The Pancakes的单曲《咁咁咁》 《咁咁咁》- The Pancakes 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :...

小小编辑
今天
108
4
流利阅读笔记30-20180719待学习

重磅:让人类得老年痴呆的竟是它? Lala 2018-07-19 1.今日导读 去年奥斯卡最佳动画长片《寻梦环游记》里有一句经典台词:“比死亡更可怕的,是遗忘”。在电影中,年迈的曾祖母会重复说一样的...

aibinxiao
今天
3
0
1.16 Linux机器相互登录

Linux机器之间以密码方式互相登录 运行命令#ssh [ip address],标准命令:#ssh [username]@ip, 如果没有写用户名,则默认为系统当前登录的用户 命令#w查看系统负载,可查看到连接到该主机的...

小丑鱼00
今天
0
0
about git flow

  昨天元芳做了git分支管理规范的分享,为了拓展大家关于git分支的认知,这里我特意再分享这两个关于git flow的链接,大家可以看一下。 Git 工作流程 Git分支管理策略   git flow本质上是...

qwfys
今天
2
0
Linux系统日志文件

/var/log/messages linux系统总日志 /etc/logrotate.conf 日志切割配置文件 参考https://my.oschina.net/u/2000675/blog/908189 dmesg命令 dmesg’命令显示linux内核的环形缓冲区信息,我们可...

chencheng-linux
今天
1
0
MacOS下给树莓派安装Raspbian系统

下载镜像 前往 树莓派官网 下载镜像。 点击 最新版Raspbian 下载最新版镜像。 下载后请,通过 访达 双击解压,或通过 unzip 命令解压。 检查下载的文件 ls -lh -rw-r--r-- 1 dingdayu s...

dingdayu
今天
1
0
spring boot使用通用mapper(tk.mapper) ,id自增和回显等问题

最近项目使用到tk.mapper设置id自增,数据库是mysql。在使用通用mapper主键生成过程中有一些问题,在总结一下。 1、UUID生成方式-字符串主键 在主键上增加注解 @Id @GeneratedValue...

北岩
今天
2
0
告警系统邮件引擎、运行告警系统

告警系统邮件引擎 cd mail vim mail.py #!/usr/bin/env python#-*- coding: UTF-8 -*-import os,sysreload(sys)sys.setdefaultencoding('utf8')import getoptimport smtplibfr......

Zhouliang6
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部