去重 | Cmq Blog

# 去重

ES6 的 Set 数据结构实现去重，由于 Set 没有重复值，再通过扩展运算符... ，将 set 数据重新构造成数组

function uniq1(arr) {
  if (!Array.isArray(arr)) return arr;
  return [...new Set(arr)];
}

1
2
3
4

利用数组的 filter 和 indexOf 去重

function uniq2(arr) {
  if (!Array.isArray(arr)) return arr;
  return arr.filter((v, index) => index === arr.indexOf(v));
}

1
2
3
4

两个数组比对

function uniq3(arr) {
  if (!Array.isArray(arr)) return arr;
  let newArr = [arr[0]];
  for (let i = 1, len = arr.length; i < len; i++) {
    //判读 arr[i]不存在 newArr 中

    /* 方法一
      if (!newArr.includes(arr[i]))   newArr.push(arr[i]);
    */

    /* 方法二
      if (newArr.indexOf(arr[i]) === -1) newArr.push(arr[i]);
    */

    // 方法三
    if (!~newArr.indexOf(arr[i])) newArr.push(arr[i]);
  }
  return newArr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

利用对属性去重，速度最快，占空间最多，空间换时间

function uniq4(arr) {
  if (!Array.isArray(arr)) return arr;
  let obj = {},
    newArr = [];
  arr.forEach(v => {
    if (!obj[v]) {
      newArr.push(v);
      obj[v] = true;
    }
  });
  return newArr;
}

1
2
3
4
5
6
7
8
9
10
11
12

利用数组方法 reduce 遍历，思路同 uniq3

function uniq5(arr) {
  if (!Array.isArray(arr)) return arr;
  return arr.reduce((newArr, current, i) => {
    if (!newArr.includes(current)) newArr.push(current);
    return newArr;
  }, []);
}

1
2
3
4
5
6
7

遍历数组有相同的就剔除掉，注意剔除后改变了原数组，下标要相应-1

function uniq6(arr) {
  if (!Array.isArray(arr)) return arr;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        arr.splice(j, 1);
        j--;
      }
    }
  }
  return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12

思路：获取没重复的最右一值放入新数组
（检测到有重复值时终止当前循环同时进入顶层循环的下一轮判断）
方法的实现代码相当酷炫

function uniq7(arr) {
  if (!Array.isArray(arr)) return arr;
  var temp = [];
  var index = [];
  for (var i = 0, l = arr.length; i < l; i++) {
    for (var j = i + 1; j < l; j++) {
      if (arr[i] === arr[j]) {
        i++;
        j = i;
      }
    }
    temp.push(arr[i]);
    index.push(i);
  }
  console.log('最右侧无重复项的下标: ', index);
  return temp;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

排序后相邻去除法

function uniq8(arr) {
  if (!Array.isArray(arr)) return arr;
  arr.sort();
  var temp = [arr[0]];
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] !== temp[temp.length - 1]) {
      temp.push(arr[i]);
    }
  }
  return temp;
}

1
2
3
4
5
6
7
8
9
10
11

# 排序

快速排序：利用递归排序

function quickSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return arr;
  let left = [],
    right = [];
  const middleValue = arr.splice(Math.round(arr.length / 2), 1)[0];
  for (let i = 0; i < arr.length; i++) {
    //升序
    if (arr[i] < middleValue) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return quickSort(left).concat(middleValue, quickSort(right));
}

1
2
3
4
5
6
7
8
9
10
11
12

冒泡排序：两两比较外层控制循环次数，比如[5,2,9,10,1] 两两交换只需要 4 次，所以-1

function bubbleSort(arr) {
  if (!Array.isArray(arr)) return arr;
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        //升序 大数下沉，小数上浮
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; //两两交换
      }
    }
  }
  return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12

选择排序：假设一个最小值索引，依次比较大小，找出剩下最小值，两两交换，每轮循环排序一位

function chooseSort(arr) {
  if (!Array.isArray(arr)) return arr;
  for (let i = 0; i < arr.length; i++) {
    //每轮循环交换一个
    let minIdx = i; //升序
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [arr[minIdx], arr[i]] = [arr[i], arr[minIdx]];
  }
  return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12

← 浏览器渲染流程 promise →