常见算法题

数组去重

双层循环

function unique(arr) {
  let res = [];
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < res.length; j++) {
      if (arr[i] === res[j]) {
        break;
      }
    }
    // 意味着 res全部扫描完都没有该元素
    if (j == res.length) {
      res.push(arr[i]);
    }
  }

  return res;
}

let test1 = [1, 1, "a", "a"];
console.log(unique(test1));

错误写法：

function unique(arr) {
  let res = [];
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < res.length; j++) {
      if (arr[i] === res[j]) {
        // 无法推入第一个数
        if (j == res.length) {
          res.push(arr[i]);
        }
        break;
      }
    }
  }

  return res;
}

indexOf 简化内层

利用 indexOf 找不到元素会返回-1

function unique(arr) {
  let res = [];
  for (var i = 0; i < arr.length; i++) {
    let cur = arr[i];
    if (res.indexOf(cur) === -1) {
      res.push(cur);
    }
  }

  return res;
}

排序后去重

先排序后比较当前元素与前一个元素，性能优于 indexof

留意该代码对边界的处理 十分巧妙

function unique(arr) {
  let res = [];
  let pre;
  let sorted = arr.concat().sort();
  for (let i = 0; i < sorted.length; i++) {
    // !i 处理第一个元素
    if (!i || pre !== sorted[i]) {
      res.push(sorted[i]);
    }
    // 下次循环之前先将这次的值赋给pre 实现与上一个元素比较
    pre = sorted[i];
  }
  return res;
}

filter

API:filter((item,index,arr)=>{})

function unique(arr) {
  let res = arr.filter((item, index, arr) => {
    return arr.indexOf(item) == index;
  });
  return res;
}

Object

我们可以发现，是有问题的，因为 1 和 '1' 是不同的，但是这种方法会判断为同一个值，这是因为对象的键值只能是字符串，所以我们可以使用 typeof item + item 拼成字符串作为 key 值来避免这个问题

function unique(arr) {
  let obj = {};
  let res = arr.filter((item, index, arr) => {
    // return obj.hasOwnProperty(item) ? false : (obj[item] = true);
    return obj.hasOwnProperty(typeof item + item)
      ? false
      : (obj[typeof item + item] = true);
  });
  return res;
}

ES6

• Set

[...new Set(arr)];

• Map

  !myMap.has(a) && myMap.set(a, 1)包含隐式转换

function unique(arr) {
  let myMap = new Map();
  return arr.filter(item => !myMap.has(a) && myMap.set(a, 1));
}

特殊类型比较

• NaN: NaN === NaN //false使用typeof NaN //number的特性
• 对象: JSON.stringify

排序算法

冒泡排序

当前项与后项比较 根据结果决定是否交换位置

ES6 解构赋值可用来交换位置[a,b] = [b,a]

function comp(arr, index) {
  let temp;
  let preI = index;
  let nextI = index + 1;
  if (arr[preI] > arr[nextI]) {
    temp = arr[preI];
    arr[preI] = arr[nextI];
    arr[nextI] = temp;
  }
  console.log(arr);
  return arr;
}

function bubble(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i; j++) {
      arr = comp(arr, j);
    }
  }
  return arr;
}

插入排序

• 先摸第一项
• 从第二项依次向后抓牌
• 和手里牌比较 两种插入情况
  • 比当前牌大 插入当前的后一位
  • 比全部都小 插入第一位

⚠️**splice(i,0,'a')会插入在 i 前面**

function insert(arr) {
  let handle = [];
  handle.push(arr[0]);
  for (let i = 1; i < arr.length; i++) {
    for (let j = handle.length - 1; j >= 0; j--) {
      if (arr[i] > handle[j]) {
        handle.splice(j + 1, 0, arr[i]);
        break;
      }
      if (j === 0) {
        handle.unshift(arr[i]);
      }
    }
  }
  return handle;
}

快速排序

• 先取出中间值
• 将原数组剩下的元素依次与中间值比较 小放左 大放右
• 递归
• 返回 拼接数组

⚠️**splice(i,1)返回值是数组 取得元素需跟[0]**

function quick(ary) {
  if (ary.length <= 1) return ary;
  let midIndex = Math.floor(ary.length / 2);
  let mid = ary.splice(midIndex, 1)[0];
  let left = [],
    right = [];
  for (let i = 0; i < ary.length; i++) {
    let item = ary[i];
    item < mid ? left.push(item) : right.push(item);
  }

  return quick(left).concat(mid, quick(right));
}