问题(来自破解编码面试):编写一个方法,从大小为 n 的数组中随机生成一组 m 个整数。 每个元素必须有相同的被选择概率。
我正在 JS 中实现我的答案。对于递归函数,代码有时会返回 undefined 作为数组中的元素之一。
我的 JS 代码
var pickMRecursively = function(A, m, i) {
if (i === undefined) return pickMRecursively(A, m, A.length);
if (i+1 === m) return A.slice(0, m);
if (i + m > m) {
var subset = pickMRecursively(A, m, i-1);
var k = rand(0, i);
if (k < m) subset[k] = A[i];
return subset;
}
return null;
};
给出的Java解决方案
int[] pickMRecursively(int[] original, int m,int i) {
if (i +1==m){// Basecase
/* return first m elements of original */
} elseif(i+m>m){
int[] subset = pickMRecursively(original, m, i - 1);
int k = random value between 0 and i, inclusive
if(k<m){
subset[k] = original[i]j
}
return subset;
}
return null;
}
最佳答案
我讨厌这些问题,因为有时它们常常故意含糊不清——我会问“数组中的数据是什么类型?”。但如果这实际上是一个关于随机重新排序数组的问题,那么在 JavaScript 中,考虑到 arr
是一个数字数组,其中一些/全部可能不是整数......
function generateM(arr) {
var hold = [];
var m = [];
var n = arr.length;
var grab;
// clone arr >> hold
while(n--) {
hold[n] = arr[n];
}
n = hold.length;
// select randomly from hold
while(n--) {
grab = hold.splice(Math.floor(Math.random()*n),1)[0];
// ensure integers
m.push(Math.round(grab));
}
return m;
}
此处克隆了数组 arr
,以解决范围问题并生成新的集合,而不是对现有集合进行重新排序。
ADDIT:或者,如果这只是要求从 n.length
数组生成一组 m.length
随机整数,那么数组的实际内容是什么并不重要,可能的(随机生成的)值的范围将是(可能是?)0 - n.length
,所以...
function generateM(arr, M) {
var aLen = arr.length;
var m = [];
do {
m.push(Math.round(Math.random() * aLen));
} while(M--);
return m;
}
...但这似乎是一个愚蠢、毫无意义的挑战。在我看来,“大小为 n 的数组”中的数据在这里非常重要。
关于javascript - JS中从大小为n的数组中随机选取m个整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34757227/