后端数据计算

Question

有这么一个文件，里面存放着99999个数字用,隔开，这些数字的范围是1-100000，

• 文件中数字没有重复并且这些数字是乱序的。
• 要求： 找到这个不存在的数字，时间复杂度，空间复杂度尽量低。
• 例如：存放着2-100000的数字，没有存放1，程序运行结束后应该返回的是这个数字 1

Answer 1

考虑用 bit 来处理，1个int是 32个数字，

(function(){
    // js 32位 0xFFFFFFFF 格式化出来是 -1，所以改16位方便演示
    const BIT_PER_SLOT = 16;

    let arrMask    = [];
    let arrMaxMask = [];
    let mapIdxNum  = {};
    let arrSlot    = [];

    let maskFull = 0;
    let maskMax  = 0;
    let numMax   = 0;

    function init()
    {
        let mask = 0x00000001;
        for(let i=0; i<BIT_PER_SLOT; i++)
        {
            arrMask.push(mask);

            maskFull = maskFull | mask;
            arrMaxMask.push(maskFull);

            mapIdxNum[mask] = i;

            mask = mask * 2;
        }

        console.log('init - mask list', arrMask);
        console.log('init - max mask list', arrMaxMask);
        console.log('init - idx num map', mapIdxNum);
    }

    function number_fmt($num)
    {
        let prefix = new Array(BIT_PER_SLOT + 1).join('0');
        return (prefix + $num.toString(2)).substr(-16);
    }

    function number_put($num)
    {
        if(numMax < $num)
            numMax  = $num;

        let idxNum  = Math.floor($num / BIT_PER_SLOT)
        let idxMask = $num % BIT_PER_SLOT;

        // 如果最大数字更新，idxNum变大，扩容 arrSlot
        for(let i=arrSlot.length; i<=idxNum; i++)
            arrSlot[i] = 0;

        arrSlot[idxNum] = arrSlot[idxNum] | arrMask[idxMask];
    }

    function number_find($arr)
    {
        // 方便其他计算，直接PUT 0，占据第一个 BIT
        number_put(0);

        // 实际处理，逐个字符读文件，转成数值，每个数值调用 number_put
        for(let i=0; i<$arr.length; i++)
            number_put($arr[i]);

        let idxMask = numMax % BIT_PER_SLOT;
        maskMax = arrMaxMask[idxMask];

        console.log('Full Mask',number_fmt(maskFull));
        console.log(' Max Mask',number_fmt(maskMax));
        let mask = maskFull;
        for(let i=0; i<arrSlot.length; i++)
        {
            if(i === arrSlot.length-1)
                mask = maskMax;

            if(arrSlot[i] !== mask)
            {
                let idx = arrSlot[i] ^ mask;
                let numBase = i * BIT_PER_SLOT;
                let numMiss = numBase + mapIdxNum[idx];

                console.log('     slot', number_fmt(arrSlot[i]));
                console.log('      idx', number_fmt(arrSlot[i] ^ mask));
                console.log('  idx num', mapIdxNum[idx]);
                console.log(' num base', numBase);
                console.log(' num miss', numMiss);

                break;
            }
        }
    }

    init();

    number_find([1,2,3,4,5,7,8,9]);
})();

Answer 2

换一个思路，python实现

def getNumb(nums):
    s = 4999950000 # sum([i for i in range(10_0000)])
    for i in nums:
        s -= i
    return s

# 题中输入为例，2-99999，返回 1
assert 1 == getNumb([i for i in range(2,10_0000)])

Answer 3

这道题如果语言环境如果支持大整数处理，还是用数学特性是最方便的，而且也容易理解，速度快，且空间占用小，就是weak_ptr的思路。
如果不支持大整数的处理，可以考虑用位运算的异或来处理，因为任何数异或本身后为0x0，而0x0异或任何数N结果还是N。而且异或的方法在支持异或的语言中都能实现。其javascript语言实现如下(其它支持位运算的语言大同小异)：

// 具体方法 
function getLoseNum( Arr ){
    rt=0x0;
    for (let i=0;i<100000;i++){
        rt=rt ^ Arr[i] ^ i ;
    }
    return (rt ^ 100000) ;
}

// 下面是测试
let arr=[]
for (let i=0;i<54640;i++) {arr.push(i+1)}
for (let i=54641;i<100000;i++) {arr.push(i+1)}
console.log( getLoseNum( arr) )

let brr=[]
for (let i=1;i<100000;i++){brr.push(i+1) }
console.log( getLoseNum( brr) )

let crr=[]
for (let i=1;i<100000;i++){crr.push(i) }
console.log( getLoseNum( crr) )

支持位运算运算异或，这个算法也是相当的快，而且空间占用，比大整数运算还小。而且这个算法实现也特别简洁。

其它诸如标记法，不但要额外占用存储空间，还需要额外遍历1次，都不如这两种方法对这种题适合。

Answer 4

随便写的，可能还有更优解，不过我懒得考虑了，抛砖引玉

List<Integer> getNumb(List<Integer> list){
    List<Integer> allNumb = new ArrayList<>();
    for (int i =1;i<=100000;i++){
      allNumb.add(i);
    }
    for (Integer numb:list){
      allNumb.remove(numb);
    }
    return allNumb;
  }

Answer 5

思路和上面的兄弟一样，只是用了数组，开销可能会更小点；

    List<Integer> getNumb(int[] nums) {
        int len = nums.length;
        int[] uses = new int[100000];
        for (int i = 0; i < len; i++) {
            uses[nums[i]] = nums[i];
        }
        List<Integer> ans = new ArrayList<>();
        for (int use : uses) {
            if (use == 0) ans.add(use);
        }
        return ans;
    }