后端数据计算
有这么一个文件，里面存放着99999个数字用,隔开，这些数字的范围是1-100000，
- 文件中数字没有重复并且这些数字是乱序的。
- 要求： 找到这个不存在的数字，时间复杂度，空间复杂度尽量低。
- 例如：存放着2-100000的数字，没有存放1，程序运行结束后应该返回的是这个数字 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]);
})();
回答：
换一个思路，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)])
回答：
这道题如果语言环境如果支持大整数处理，还是用数学特性是最方便的，而且也容易理解，速度快，且空间占用小，就是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次，都不如这两种方法对这种题适合。
回答：
随便写的，可能还有更优解，不过我懒得考虑了，抛砖引玉
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;
}
回答：
思路和上面的兄弟一样，只是用了数组，开销可能会更小点；
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;
}
以上是 后端数据计算 的全部内容， 来源链接： utcz.com/p/944177.html
