打乱数组（网易）
解题思路：
-
从前往后尝试填充 [0, n - 1] 该填入什么数时，通过当前下标随机与（剩余的）哪个下标进行值交换来实现；
-
对于下标 x 而言，从 [x, n - 1] 中随机出一个位置与 x 进行值交换；
- random 默认区间是[0，1）的随机数；
- 在 [n，m] 区间随机取一个数，Math.floor(Math.random() * (m - n + 1)) + n;
复杂度：
-
时间复杂度：
- 初始化：O(n)，其中 n 为数组中的元素数量；
-reset：O(1)； - shuffle：O(n)，只需要遍历 n 个元素即可打乱数组；
- 初始化：O(n)，其中 n 为数组中的元素数量；
-
空间复杂度：O(n)，记录初始状态需要存储 nn 个元素；
代码实现：
TS
JS
class Solution {
nums: Array<number>;
constructor(nums: number[]) {
this.nums = nums;
}
reset(): number[] {
return this.nums;
}
shuffle(): number[] {
let arr = [...this.nums];
let n = arr.length;
for (let i = 0; i < n; i++) {
// 从 i 到 n-1 随机选一个
const rand = randOne(i, n - 1);
// 交换nums数组i和rand下标的两个元素
[arr[i], arr[rand]] = [arr[rand], arr[i]];
}
return arr;
}
}
// 获取闭区间 [n, m] 内的一个随机整数
function randOne(n, m) {
return Math.floor(Math.random() * (m - n + 1)) + n;
}
var Solution = function (nums) {
this.nums = nums;
};
Solution.prototype.reset = function () {
return this.nums;
};
Solution.prototype.shuffle = function () {
let arr = [...this.nums];
let n = arr.length;
for (let i = 0; i < n; i++) {
// 从 i 到 n-1 随机选一个
const rand = randOne(i, n - 1);
// 交换nums数组i和rand下标的两个元素
[arr[i], arr[rand]] = [arr[rand], arr[i]];
}
return arr;
};
// 获取闭区间 [n, m] 内的一个随机整数
function randOne(n, m) {
return Math.floor(Math.random() * (m - n + 1)) + n
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
148.排序链表
上一篇
评论
