关于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

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

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

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

1. 循环遍历实现

2. BitSet 实现

3、简略理解一下BitSet

3.1 形成

3.2 构造函数

3.3 set办法

3.3 get办法

3.4 其余办法

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

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

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

1. 循环遍历 实现

2. BitSet 实现

3、简略理解一下BitSet

3.1 形成

3.2 构造函数

3.3 set办法

3.3 get办法

3.4 其余办法

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

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

1. 循环遍历实现

发表回复取消回复