shuffle

leetcode算法篇，常见算法总结

打乱数组More info: leetcode384

题目描述简化

给你一个数组，对其进行随机打乱

关键问题就是随机化操作，要保证数组中每一个数字在某一个位置出现的机率是等可能的。可以从后面往前面进行遍历，因为这样方便设置随机位置
随机位置j = Math.floor(Math.random() * (i + 1));

具体实现

这里对leetcode代码做了简化

function shuffle(array) {
  // 这里考虑从后面往前面进行遍历，不容易出错
  for(let i = array.length - 1; i > 0; --i){
    let j = Math.floor(Math.random() * (i + 1));//这里一定要进行加1操作，因为这样可以任意一个数字可以和自己进行交换
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  return array;
}

// 测试
console.log(shuffle([1,2,-2,3]));

分析总结

注意点：
1、保证随机化的操作，必须保证随机的下标只能在没有遍历的范围中随机
2、从后往前遍历更容易确定随机的下标
3、随机的下标必须包含当前下标自身