从JS中一个大小为n的数组中随机选取m个整数
Pick m integers randomly from an array of size n in JS
问题(来自破解编码面试):编写一个方法,从大小为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的数组"中的数据在这里非常重要。
相关文章:
- Jquery/Javascript:通过按下按钮显示数组中的随机图像
- Javascript-从随机的单词数组中创建段落
- JavaScript-从对象数组中输出随机OBJECT
- 数组中的随机文本字符串
- Javascript从数组中随机选择并按字母顺序排列
- 如何在数组javascript中选择伪随机值
- 从数组中随机抽取的最佳方式
- 在两个位置显示数组中的随机单词
- 从数组中随机采样子集
- Javascript - 如何按顺序从数组中挑选随机元素
- Javascript 数组随机丢失一个元素
- Javascript从数组中选择一个随机对象集
- 如何从包含1000个项目的数组中随机选择一个项目
- 从数组中随机选择项,仅在以前未使用过时使用
- 选择数组的随机元素来设置Youtube视频ID API
- 如何从字符串数组中获得8个随机唯一元素
- 在Javascript中从数组中挑选一个随机变量
- 尝试使用Javascript在数组中创建一个带有随机选择页面的链接
- Javascript:创建一个随机数学方程数组作为对象,20次
- 从Javascript记录数组中选择随机项,并将其转换为数组