一道面试题
发布于 4 个月前 作者 SHocker-Yu 1397 次浏览 来自 问答

是这样,早上的一个面试题,题目是:随机取100个数,范围1~100,不可重复(即1,2,3,4,5,6,…,98,99,100,不能用递增方法)。 我的现场答案是: var array = []; var i = 0; var randomNumber; while ( i < 100 ) { randomNumber = Math.ceil(Math.random()*100);//1-100随机整数 if(array.indexOf(randomNumber) === -1) { array.push(randomNumber); i++; }

} 但是面试官说一个问题,100个数中,有可能其中一个数一直随机不到,是不是会陷入死循环,再接着放大范围,比如取1000个数,范围1~1000,不可重复,以此类推1万个数等等,是不是更容易无限死循环一直随机不到某些数,我觉得他说的有道理,现场我没有想出更好的解决办法,但是直到现在我也没有想到,是不是我思路就不对?有什么更好的解决办法吗?

17 回复

这还不简单,用随机数做为hash,如果已经有了,就是 hash conflict,顺着往下找空就好了。

好吧,刚刚问了面试官。 是我理解错面试口述时的意思了,面试官只是想要打乱1-100的顺序数组,当我说for(let i = 1; i < 100; i++)取100个数时,他说不要顺序的100个数,我没理解对,下意识的以为是要随机生成100个数,而不是在顺序数组的基础上打乱就可以了。

@SHocker-Yu 你需要的是一个洗牌函数

_.shuffle([1, 2, 3, 4]); // => [4, 1, 3, 2]

https://lodash.com/docs/4.17.4#shuffle

@SHocker-Yu 给你个思路, 把1-100 分成四个数组, 然后1-4随机对应index 换元素 自豪地采用 CNodeJS ionic

// 1-100 顺序数组
const arr = Array.from((new Array(101)).keys()).slice(1);
const newArr = [];

while(arr.length > 0) {
  const randomIndex = Math.floor(Math.random() * arr.length);
  newArr.push(arr[randomIndex]);
  arr.splice(randomIndex, 1);
}
console.log(newArr);
function shuffle(array) {
  const length = array == null ? 0 : array.length
  if (!length) {
    return []
  }
  let index = -1
  const lastIndex = length - 1
  const result = copyArray(array)
  while (++index < length) {
    const rand = index + Math.floor(Math.random() * (lastIndex - index + 1))
    const value = result[rand]
    result[rand] = result[index]
    result[index] = value
  }
  return result
}

https://github.com/lodash/lodash/blob/4f3ef2e8d8ea9e91f5c6b80b65c3fd5585699af3/shuffle.js

@dfsq1311为啥是 ++index < length 不是 ++index < length/2 ??

一个比较简单的方法

  arr.map((e, i) => {
    const rnd = Math.floor(Math.random() * arr.length);
    let t = arr[i];
    arr[i] = arr[rnd];
    arr[rnd] = t;
  });

这种方法并不是随机打乱数组,会有较大偏差,比如打乱后的arr[0]=2的概率较高,arr[1]=3的概率较高 随机打乱看5楼6楼

@lei2231 我的想法是,既然是洗牌函数,有个条件就是所有元素都需要进行洗牌,++index < length可以保证将所有元素都与rand随机位置的元素做了交换,洗牌是彻底的。 ++index < length/2, 问题在于洗牌不够彻底,理论上讲,当length足够大的时候,++index < length/2这种洗牌,后半部分有一半的数据(总体的四分之一)并没有进行过洗牌,位置不会变

大家都这么正经,我来抖个机灵 ㄟ( ▔, ▔ )ㄏ


const arr = [1, 2, 3, 4, 5, 6]; const temp = []; const result = await arr.map(num => { setTimeout(() => { temp.push(num); }, Math.floor(Math.random() * 1000)) });

setTimeout(() => { console.log(‘temp’, temp); }, 1000)


@danielsss hah,多谢,是我理解错了,但是理解错误后的题目也挺有意思的我觉得。

@beyond5959 其实只要涉及到Math.random(),范围越大,计算量越大,耗费的时间就越长

用减法就行了。取一个减少一个

那就洗吧 let arr = Array.from((new Array(101)).keys()).slice(1); let len = arr.length let res = [] while (len-- > 0) { let rand = Math.floor(Math.random() * len); res.push(arr[rand]) arr[rand] = arr[len] }

这根本不是啥随机玩法,你需要的是打乱这100个数字就可以了。 具体实现参考 lodash(underscore) 的 _.shuffle 方法

回到顶部