共计 3853 个字符，预计需要花费 10 分钟才能阅读完成。
一个枯燥递增的数组 被人随机拿出一个数 你怎么找到这个数
就以 1,2,3,4,5,6,7,8,9… 100 为例吧 小强把 88 这个数拿了进去 我怎么能很快找到？
1. 循环遍历 实现
认为的思维，我是想到了循环遍历，比拟后一个数字是不是比前一个数字大 1 不是的话 那就是少了以后比拟值的后一个值。
貌似可能解决问题，然而如果随机剔除两个呢？那就废了 须要无休止的加 if else
/**
* @author 木子的昼夜
*/
public class ConcurrnetTest {public static void main(String[] args){ConcurrnetTest test = new ConcurrnetTest();
Integer[] arr = test.get();
System.out.println(test.findByFor(arr));
// 或者是间接比拟下标
System.out.println(test.findByFor02(arr));
}
// 遍历找数
private Integer findByFor(Integer[] arr) {
Integer res = null;
// 头尾解决 如果剔除的是 1 或者 100
if(arr[0] != 1) {return 1;}
if (arr[arr.length-1] != 100) {return 100;}
for (int i = 0; i < arr.length-1; i++) {
// 如果后一个不等于前一个 +1 那就是被剔除了
if (arr[i]+1 != arr[i+1]) {res = arr[i]+1;
break;
}
}
return res;
}
// 遍历找数
private Integer findByFor02(Integer[] arr) {
Integer res = null;
// 100 如果被剔除 检测不到 须要非凡解决
if (arr[arr.length-1] != 100) {return 100;}
for (int i = 0; i < arr.length; i++) {
// 下标 +1 不等于对应下表元素 就是有问题
// 0:1 1:2 2:3 ....
if (arr[i] != (i+1)) {
res = i+1;
break;
}
}
return res;
}
/**
* 获取 1 到 100 剔除 88
* @return
*/
public Integer[] get(){List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 100; i++) {if (i != 88) {list.add(i);
}
}
return list.toArray(new Integer[0]);
}
}2. BitSet 实现
能够想一下 1 到 100 是有序的枯燥递增的 咱们能够这样示意吗？
咱们用一个 bit 数组来标识是否呈现数据，bit 为 0 示意数据没呈现，bit 为 1 示意数据呈现
这样咱们就能够遍历 arr 而后设置 bit 对应的位（为 1），最初遍历 bit 看看那个位是 0 那就是短少这个数据
伪代码：
// 为什么 101 个 因为蕴含 0 bit 数组默认都是 0
bit[] bits = new bit[101];
// 遍历数组 数组中有 1 到 100 剔除 88
for (int i = 0; i < arr.length; i++) {
// 设置对应的下标为 1
bits[arr[i]] = 1;
}java 中 bit 数组不好实现 咱们能够用 int 或者 long 的某一个二进制位示意
为什么要本人写？难道大佬没有给咱们提供轮子？
有的：java.util.BitSet
实现代码：
/**
* @author 木子的昼夜
*/
public class ConcurrnetTest02 {public static void main(String[] args){ConcurrnetTest02 test = new ConcurrnetTest02();
Integer[] arr = test.get();
// 循环形式获取
System.out.println(test.findByBitSet(arr));
}
// 遍历找数
private Integer findByBitSet(Integer[] arr) {
// 从 0 到 100
BitSet bitSet = new BitSet(101);
for (int i = 0; i <arr.length ; i++) {bitSet.set(arr[i]);
}
// 从 1 开始 到 100 看哪个位是 false 那就是哪个位没有值
// 这里的 1 100 都能够写成参数 或者是配置 具体看本人实现
for (int i = 1; i <=100 ; i++) {if (!bitSet.get(i)){return i;}
}
return null;
}
/**
* 获取 1 到 100 剔除 88
* @return
*/
public Integer[] get(){List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 100; i++) {if (i != 88) {list.add(i);
}
}
return list.toArray(new Integer[0]);
}
}应用 BitSet 不论随机摘除几个数据，逻辑都很简略 set get 两个办法就够
这里 BitSet 用着简略，次要思考的是这个 BitSet 知识点 BitSet 还能够对海量数据统计 等
3、简略理解一下 BitSet
3.1 形成
private long[] words; 用的 long 数组来标记的 一个 long 类型 = 8 字节 = 8*8 位 = 64 能示意 64 个数
3.2 构造函数
// 指定默认大小
public BitSet(int nbits) {
// 不能是正数 0 也是能够的
if (nbits < 0)
throw new NegativeArraySizeException("nbits < 0:" + nbits);
// 初始化大小
initWords(nbits);
// 标记一下是否用户指定了大小
sizeIsSticky = true;
}
private void initWords(int nbits) {
// 算一下须要多少个 64 也就是多少个 long 而后初始化数据库
words = new long[wordIndex(nbits-1) + 1];
}
/**
* ADDRESS_BITS_PER_WORD：6
*/
private static int wordIndex(int bitIndex) {
// >> 6 相当于 除以 64 2^6=64
return bitIndex >> ADDRESS_BITS_PER_WORD;
}3.3 set 办法
设置指定数值为 true
public void set(int bitIndex) {
// 非法 bit 地位
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0:" + bitIndex);
// 算一下这个地位对应 long 数组的哪个下标 bitIndex/64
int wordIndex = wordIndex(bitIndex);
// 查看是否须要扩容 需要的话间接扩容 默认扩大 2 *words.length
// 如果 wordIndex>2*words.length 那就扩大到 wordIndex 大小
expandTo(wordIndex);
// 就是这个操作 设置了对应地位为 1
// 1L << bitIndex 这句话就是把 bitIndex 转换为程序想要的 bitindex
// 比方：10 ==》10000000000
// 而后 或运算 或就是只有一个为 1 就为 1
words[wordIndex] |= (1L << bitIndex); // Restores invariants
checkInvariants();}
3.3 get 办法
获取指定数值是否存在 存在返回 true 不存在返回 false
public boolean get(int bitIndex) {
// 非法判断
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0:" + bitIndex);
// 检测了个什么货色
checkInvariants();
// 获取下标
int wordIndex = wordIndex(bitIndex);
// 小于 wordsInUse（在用数组最大下标）这里用的 & 对应下标是 1 才返回 true
return (wordIndex < wordsInUse)
&& ((words[wordIndex] & (1L << bitIndex)) != 0);
}3.4 其余办法
clear() 清空所有 设置所以位为 false
clear(int bitIndex) 设置指定下标为 false
BitSet get(int fromIndex, int toIndex) 获取某个范畴的值 返回 BitSet
set(int bitIndex, boolean value) 设置指定地位 true 或 false
set(int fromIndex, int toIndex) 设置某个范畴数据为 true
set(int fromIndex, int toIndex, boolean value) 设置某个范畴数据为 true 或 false
clear(fromIndex, toIndex); 设置指定范畴为 false
and(BitSet set) 合并 BitSet 到本人 用的 & 对应地位都为 1 后果：就是 1
or(BitSet set) 合并 BitSet 到本人 用的 | 对应地位只有有一个是 1 后果：就是 1
xor(BitSet set) 合并 BitSet 到本人 用的 ^ 对应地位一个位 1 一个为 0 后果：就是 1
andNot(BitSet set) 合并 BitSet 到本人 用的 & ~ 原地位为 1 set 对应地位为 0 后果：就是 1 有问题能够留言，或者公众号留言（回复快）：
正文完
