第76题 怎么在制定数据源里面生成一个长度为 n 的不重复随机数组 能有几种方法 时间复杂度多少（字节）

第一版 时间复杂度为 O(n^2)

    function getTenNum(testArray, n) {
      let result = [];
      for (let i = 0; i < n; ++i) {
        const random = Math.floor(Math.random() * testArray.length);
        const cur = testArray[random];
        if (result.includes(cur)) {
          i--;
          break;
        }
        result.push(cur);
      }
      return result;
    }
    const testArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
    const resArr = getTenNum(testArray, 10);

第二版 标记法 / 自定义属性法 时间复杂度为 O(n)

    function getTenNum(testArray, n) {
      let hash = {};
      let result = [];
      let ranNum = n;
      while (ranNum > 0) {
        const ran = Math.floor(Math.random() * testArray.length);
        if (!hash[ran]) {
          hash[ran] = true;
          result.push(ran);
          ranNum--;
        }
      }
      return result;
    }
    const testArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
    const resArr = getTenNum(testArray, 10);

第三版 交换法 时间复杂度为 O(n)

    function getTenNum(testArray, n) {
      const cloneArr = [...testArray];
      let result = [];
      for (let i = 0; i < n; i++) {
        debugger;
        const ran = Math.floor(Math.random() * (cloneArr.length - i));
        result.push(cloneArr[ran]);
        cloneArr[ran] = cloneArr[cloneArr.length - i - 1];
      }
      return result;
    }
    const testArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
    const resArr = getTenNum(testArray, 14);

值得一提的是操作数组的时候使用交换法 这种思路在算法里面很常见

最终版 边遍历边删除 时间复杂度为 O(n)

    function getTenNum(testArray, n) {
      const cloneArr = [...testArray];
      let result = [];
      for (let i = 0; i < n; ++i) {
        const random = Math.floor(Math.random() * cloneArr.length);
        const cur = cloneArr[random];
        result.push(cur);
        cloneArr.splice(random, 1);
      }
      return result;
    }
    const testArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
    const resArr = getTenNum(testArray, 14);