面试题：一个单调递增的数组随机拿出一个数你怎么找到这个数

原创

木子的昼夜

修改于 2021-04-06 11:05:20

3790

修改于 2021-04-06 11:05:20

文章被收录于专栏：互联网底层的我们互联网底层的我们

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

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

欢迎关注公众号：

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

登录后参与评论

0 条评论

热度