算法题（洗牌算法）
【算法题（洗牌算法）】以前面试的时候考过洗牌算法，当时写的比较简陋，核心思路如下：
- 创建一个空的结果数组；
- 依次从原数组中随机取样，然后按顺序
push到结果数组中； - 为防止出现碰撞，每次取样后，将该元素从原数组删除；
其实还有一种思路，按顺序从原数组中获取元素，然后放到新数组的随机位置，但是这样无法消除碰撞的问题
function shuffle(arr) {
let len = arr.length;
let res = [];
for (let i=0;
i可以看到上面的代码存在两个问题：
- 创建新数组，导致使用了额外空间；
- 从数组中删除元素需要移动其他元素下标，导致总的时间复杂度为
O(n^2)；
- 从数组最后一个元素开始倒序遍历；
- 从包含当前元素在内的数组中，随机抽取元素，与当前元素交换；
- 不断往前遍历，直到所有元素都被交换；
function randomIndex(index: number): number {
return Math.floor(Math.random() * (index + 1));
}function swap(arr: T[], a: number, b: number) {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}export function shuffle(arr: T[]): T[] {
for (let i=arr.length-1;
i>=0;
i--) {
let r = randomIndex(i);
swap(arr, r, i);
}
return arr;
}const res = shuffle([1, 2, 3, 4, 5, 6]);
console.log(res);
从代码中可以看出，每一步都是从数组中随机抽取元素，放到数组的最后，然后指针前进一位，继续从剩下数组中抽取元素，放到数组的最后。按这个过程依此类推，最终整个数组的元素就被打乱了。实现的思路其实和本人之前的代码是一样的，但是有两点改进：
- 没有创建新数组，空间复杂度为
O(n)； - 通过元素交换的方法，避免了从数组中删除元素导致需要移动其他元素下标的问题，时间复杂度为
O(n)；
推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- jhipster|jhipster 升级无效问题
- “精神病患者”的角度问题
- 画解算法（1.|画解算法：1. 两数之和）
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- Guava|Guava RateLimiter与限流算法
- 解决SpringBoot引用别的模块无法注入的问题
- leetcode|leetcode 92. 反转链表 II
- 迷茫是人生常态
- Hive常见问题汇总