乐趣区

关于javascript:算法题洗牌算法

jiezi

以前面试的时候考过洗牌算法，过后写的比拟简陋，外围思路如下：

  • 创立一个空的后果数组；
  • 顺次从原数组中随机取样，而后按程序 push 到后果数组中；
  • 为防止出现碰撞，每次取样后，将该元素从原数组删除；

其实还有一种思路，按程序从原数组中获取元素，而后放到新数组的随机地位，然而这样无奈打消碰撞的问题 

function shuffle(arr) {
  let len = arr.length;
  let res = [];
  for (let i=0; i<len; i++) {res.push(sample(arr));
  }
  return res;
}

function sample(arr) {
  // 数组随机取样
  let randIndex = Math.floor(Math.random() * arr.length);
  // 获取元素并从原数组中删除
  let [ele] = arr.splice(randIndex, 1);
  return ele;
}

能够看到下面的代码存在两个问题：

  • 创立新数组，导致应用了额定空间；
  • 从数组中删除元素须要挪动其余元素下标，导致总的工夫复杂度为 O(n^2)；

那么有没有一种办法能够不创立新数组，间接在原数组上批改呢？明天看到一种 Fisher-Yates 洗牌算法，思路与下面代码相似，但没有创立新数组，而是采纳了与快排相似的元素替换办法:

  • 从数组最初一个元素开始倒序遍历；
  • 从蕴含以后元素在内的数组中，随机抽取元素，与以后元素替换；
  • 一直往前遍历，直到所有元素都被替换；
function randomIndex(index: number): number {return Math.floor(Math.random() * (index + 1));
}

function swap<T>(arr: T[], a: number, b: number) {let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

export function shuffle<T>(arr: T[]): T[] {for (let i=arr.length-1; i>=0; i--) {let r = randomIndex(i);
    swap<T>(arr, r, i);
  }
  return arr;
}

const res = shuffle<number>([1, 2, 3, 4, 5, 6]);
console.log(res);

从代码中能够看出，每一步都是从数组中随机抽取元素，放到数组的最初，而后指针后退一位，持续从剩下数组中抽取元素，放到数组的最初。按这个过程依此类推，最终整个数组的元素就被打乱了。实现的思路其实和自己之前的代码是一样的，然而有两点改良：

  • 没有创立新数组，空间复杂度为 O(n)；
  • 通过元素替换的办法，防止了从数组中删除元素导致须要挪动其余元素下标的问题，工夫复杂度为 O(n)；
退出移动版