关于java:面试题-一个单调递增的数组-随机拿出一个数-你怎么找到这个数

一个枯燥递增的数组 被人随机拿出一个数 你怎么找到这个数

就以 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 

有问题能够留言，或者公众号留言（回复快）：