1. 数组中是否存在某个值？
数组自带方法
var arr = [1, 2, 4, 3, 5, 6]console.log(arr.includes(4))console.log(arr.some(item => item === 4))console.log(arr.find(item => item === 4))console.log(arr.findIndex(item => item === 4))console.log(arr.indexOf(4) !== -1)console.log(arr.filter(item => item === 4))// for 循环，略其他各种"神奇"的算法
- 先排序，然后二分法查找
- set 解法，利用 set 的唯一性，将目标值添加进 set，如果 set 长度没变的话，这个值就是存在的
var arr = [1,2,3,4,5,6]var arrSet = new Set(arr)let prevSetLen = arrSet.sizearrSet.add(5)console.log(prevSetLen===arrSet.length)- 利用数组的 join 方法，把所有数字用逗号拼起来，然后正则匹配，或是调 includes 方法
2. 找出两个数组中的交集？
常规蠢办法
- for 循环
var arr1 = [1, 2, 3]var arr2 = [3, 4, 5, 6]var commonArr = []for (var i = 0; i < arr1.length; i++) { var _item = arr1[i] for (var j = 0; j < arr2.length; j++) { if (_item === arr2[j]) { commonArr.push(_item) } }}- ES6 的 filter 结合 includes 方法
var arr1 = [1, 2, 3]var arr2 = [3, 4, 5, 6]arr1.filter(item=>arr2.includes(item))- 一个数组转对象，一个数组遍历看对象是否存在对应值
var arr1 = [1, 2, 3]var arr2 = [3, 4, 5, 6]var _obj = {}let _tempArr = arr1.length > arr2.length ? arr2 : arr1_tempArr.forEach(item => { _obj[item] = item})let commonArr = arr2.filter(item => _obj[item])console.log(commonArr)_obj = null_tempArr = null这里先判断数组长度，选一个短的数组，使得新创建的临时对象尽可能小。
- 如果不考虑单个数组里有重复项的话，可以先合并数组，然后再遍历合并后的数组，进行计次，大于2则是重叠的。
var arr1 = [1, 2, 3]var arr2 = [3, 4, 5, 6]var _tempArr = arr1.concat(arr2).sort()var result = []_tempArr.reduce((prev, now) => { if (prev === now) { result.push(now) } return now})- set 的使用，主要利用不可重复设置，判断长度是否有变化，而得出是否是重复了；或者直接用 has 方法
var arr1 = [1, 2, 3]var arr2 = [3, 4, 5, 6]var set = new Set(arr1)var result = []result = arr2.filter(item => arr1.has(item))console.log(result)"神奇"的算法
- 排序后，两个数组下标移动，两两比较
var arr1 = [1, 2, 8, 3 ]var arr2 = [5, 6, 2, 3, 4]arr1.sort() // [1,2,3]arr2.sort() // [2,3,4,5,6]var result = []let arr1Index = 0let arr2Index = 0let runTimes = 0while (arr1Index < arr1.length && arr2Index < arr2.length) { runTimes++ let arr1Item = arr1[arr1Index] let arr2Item = arr2[arr2Index] if (arr1Item > arr2Item) { arr2Index++ } else if (arr1Item < arr2Item) { arr1Index++ } else { result.push(arr1Item) arr1Index++ arr2Index++ }}console.log(result)console.log(runTimes) 3.两个数组的并集？
- set
var arr1 = [1, 2, 3]var arr2 = [4, 5, 3, 6]var result = [...new Set(arr1.concat(arr2))]// var result = [...new Set([...arr1, ...arr2])]- reduce
var arr1 = [1, 2, 3]var arr2 = [4, 5, 3, 6]var tempArr = [...arr1, ...arr2].sort()var result = []tempArr.reduce((prev, now) => { if (prev !== now) { result.push(now) } return now}, null)console.log(result)- 转 json 对象
var arr1 = [1, 2, 3]var arr2 = [4, 5, 3, 6] var obj = {}arr1.forEach(item => (obj[item] = item))arr2.forEach(item => (obj[item] = item))var result = Object.values(obj)console.log(result)4. 数组去重？
效率上讲，转 obj 的方式 > set > reduce > includes/indexOf > 双重for循环
- 双重for循环
var arr1 = [1, 2, 3, 3, 4, 5, 6, 8]var result = []for (var i = 0; i < arr1.length; i++) { let _hasItem = false for (var j = 0; j < result.length; j++) { if (arr1[i] === result[j]) { _hasItem = true break } } if (!_hasItem) { result.push(arr1[i]) }}console.log(result)- includes/indexOf
var arr1 = [1, 2, 3, 3, 4, 5, 6, 8]var result = []arr1.forEach(item => { if (!result.includes(item)) { result.push(item) }})- reduce
var arr1 = [1, 2, 4, 5, 3, 3, 3, 6, 8]arr1.sort()var result = []arr1.reduce((prev, now) => { if (now !== prev) { result.push(now) } return now}, null)- set
var arr1 = [1, 2, 4, 5, 3, 3, 3, 6, 8]var result = [...new Set(arr1)]- 转对象方式
var arr1 = [1, 2, 4, 5, 3, 3, 3, 6, 8]var obj = {}arr1.forEach(item => (obj[item] = item))var result = Object.values(obj)5. 数组排序？
自带 sort
var arr = [2,3,1,4,6]arr.sort(); // [1,2,3,4,6]arr.sort((a,b)=>a-b); // [1,2,3,4,6]arr.sort((a,b)=>b-a); // [6,4,3,2,1]选择排序
每一次选择遍历选择一个最小值，确定一个位置
var times = 0function selectSort(arr) { // 没遍历一轮,将确定一个位置 for (var i = 0; i < arr.length; i++) { // 假定当前项是剩余未排中最小的 let minIndex = i // 从已经确定的位置之后一位开始遍历 for (var j = i + 1; j < arr.length; j++) { // 假如找到比 min 还小的,更新最小值 if (arr[j] < arr[minIndex]) { minIndex = j } } // 得到最小值,第i位确定 let temp = arr[i] arr[i] = arr[minIndex] arr[minIndex] = temp }}冒泡排序
核心为两两按大小规则交换
function bubbSort(arr) { for (var i = 0; i < arr.length; i++) { // 74 for (var j = i + 1; j < arr.length; j++) { // 如果后面一个大于前面一个,那么换位置 if (arr[j] < arr[i]) { var temp = arr[j] arr[j] = arr[i] arr[i] = temp } } }}快速排序
- 先随机选一个数(可选中间值)
- 以这个数分组，小的放左边，大的放右边
- 同理，在左边和右边的分组执行相同的操作，直到分组只剩一个元素
var arr = [74, 28, 60, 41, 29, 90, 52, 40]function quickSort(arr){ // 递归出口 if(arr.length<=1){ return arr } // 1. 选中值 var basicNum = arr[Math.floor((arr.length - 1) / 2)] // 2. 左右分组 var left = [] var right = [] arr.forEach(item=>{ if(item>basicNum){ right.push(item) } else{ left.push(item) } }) // 3.递归执行左边和右边数组,并且合并结果 return quickSort(left).concat(basicNum, quickSort(right))}最简单也是空间复杂度高的排序，当前只能理解到这种了，以后理解了优化的再更新。????
归并排序，插入排序以后有时间再总结下