文档章节

数组中存放0到n中的缺少一个数的连续数,找出该缺少的数

一贱书生
 一贱书生
发布于 2016/11/19 10:36
字数 378
阅读 56
收藏 0

最低有效位(Least Significant Bit)代表二进制数中的最小的单位,可以用来指示数字很小的变化。也就是说,LSB是一个二进制数字中的第0位(即最低位),具有权值为2^0,可以用它来检测数的奇偶性。在大端序中,lsb指最右边的位。

   最高有效位the Most Significant Bitmsb),是指一个n位二进制数字中的n-1位,具有最高的权值2^n − 1。与之相反的称之为最低有效位。在大端序中,msb即指最左端的位。对于有符号二进制数,负数采用反码或补码形式,此时msb用来表示符号,msb为1表示负数,0表示正数。

   注意:

    (1)MSB(全大写)有时也指the Most Significant Byte,指多字节序列中具有最大权重的字节。

     (2)LSB(全大写)有时也指Least Significant Byte,指多字节序列中最小权重的字节。

 

public int findMissing(ArrayList<BitInteger> array)
{
/*
bit 0对应于LSB.以此为起点,逐步向较高的位推进
*/
return findMissing(array,0);
}
public int findMissing(ArrayList<BitInteger> input,int column)
{
if(column>=BitInteger.INTEGER_SIZE)//终止条件或错误条件
{
return 0;
}
ArrayList<BitInteger> oneBits=new ArrayList<BitInteger>(input.size()/2);
ArrayList<BitInteger> zeroBits=new ArrayList<BitInteger>(input.size()/2);
for(BitInteger t:input)
{
if(t.fetch(column)==0)
{
zeroBits.add(t);
}
else
{
oneBits.add(t);
}
}
if(zeroBit.size()<=oneBits.size())
{
int v=findMissing(zeroBits,column+1);
return (v<<1)|0;
}
else
{
int v=findMissing(oneBits,column+1);
return (v<<1)|1;
}
}

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
LeetCode算法题-Missing Number(Java实现-四种解法)

这是悦乐书的第200次更新,第209篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第65题(顺位题号是268)。给定一个包含n个不同数字的数组,取自0,1,2,...,n,找到数组中缺少...

小川94
前天
0
0
编程题——31~40

三十一、连续子数组的最大和 输入一个整数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 三十二、从1到n整数中...

thanatos_y
2016/07/26
13
0
计算机等级考试三级网络技术上机题(11)

函数ReadDat( )实现从文件IN83.DAT中读取1000个十进制整数到数组xx中。请编制函数Compute( )分别计算出xx中偶数的个数even、奇数的平均值ave1、偶数的平均值ave2及所有偶数的方差totfc的值,...

等级考试
2014/12/22
0
0
面试精选之位操作问题集锦

Java 中位运算符有与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)、无符号右移(>>>),只针对 int 类型有效,也可以作用于 byte、short、char、long,当为这四种类型时,J...

JohnnyShieh
2017/12/28
0
0
几个算法题

1 在一个字符串中找到第一个只出现一次的字符,如输入abac,则输出b 本题看似很简单,开个长度为256的表,对每个字符hash计数就可以了,但很多人写的代码都存在bug,可能会发生越界访问。这是...

泳泳啊泳泳
2017/12/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

设计模式“6”大原则!

面向对象设计原则 概述 对于面向对象软件系统的设计而言,在支持可维护性的同时,提高系统的可复用性是一个至关重要的问题,如何同时提高一个软件系统的可维护性和可复用性是面向对象设计需要...

Java干货分享
20分钟前
1
0
mybatis学习(1)

JDBC连接方式: 1.底层没有使用连接池,操作数据库需要频繁的创建和关闭连接,消耗资源。 2.写原生的JDBC代码在JAVA中,一旦需要修改SQL的话(比如表增加字段),JAVA需要整体重新编译,不利...

杨健-YJ
今天
4
0
怎么组织文档

可以从以下几个方面考虑组织文档: ☐ 各种分支的界面截图和对应的类及文件 ☐ 框架或类图 ☐ 流程图 ☐ 时序图 ☐ 注意事项

-___-
今天
4
0
分布式之数据库和缓存双写一致性方案解析

引言 为什么写这篇文章? 首先,缓存由于其高并发和高性能的特性,已经在项目中被广泛使用。在读取缓存方面,大家没啥疑问,都是按照下图的流程来进行业务操作。 但是在更新缓存方面,对于更...

别打我会飞
今天
19
0
我的oracle11G,12c OCM之路

ocm认证感悟 ---------------------- 距离拿到ocm证书已经过了1年的时间,当初拿到证书的心情到现在还记得。其实在每个DBA心里都有一个成为强者的梦想,需要被认可,我也一样。我干过开发,做...

hnairdb
今天
7
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部