都是血的教训啊,为什么没早点刷点面试题……
数组扁平化
1. 递归
const flatten1 = (arr) => { let temp = []; for(let item of arr) { if(item instanceof Array) { temp = [...temp, ...(fn1(item))]; } else { temp.push(item) } } return temp; }
2. toString()和split()
let arr1 = [1, 2, [3, [4, [5, 6, 7, 'haha', 8]], [9, 10, [11, 12]]]] const flatten2 = (arr) => { let str = arr.toString(); return str.split(',') } console.log(flatten2(arr1)) // [ '1', '2', '3', '4', '5', '6', '7', 'haha', '8', '9', '10', '11', '12' ] // 可以看出来这种方法的缺陷在于把所有的元素都变成string了
3. reduce
const flatten3 = (arr) => { return arr.reduce((previous, current) => { return previous.concat(Array.isArray(current) ? fn3(current) : current) }, []); }
4. concat结合解构
const flatten4 = (arr) => { while(arr.some(item => Array.isArray(item))) { arr = [].concat(...arr); // 这里其实相当于给concat传了多个参数,假如是数组的参数就解构 } return arr; }
数组去重
1. indexOf
这种方法在使用时,每一个元素都要使用indexOf去判断一下,这就依赖于indexOf的效率了,假如indexOf是遍历res数组的话,那么效率就是O(n),整体就是O(n^2)
let array = [1, 1, '1']; const unique1 = (array) => { var res = []; for (let i = 0, len = array.length; i < len; i++) { var current = array[i]; if (res.indexOf(current) === -1) { res.push(current) } } return res; } console.log(unique1(array));
2. 排序后去重
取决于排序的效率,假如采用内置的sort可以达到O(nlogn)
const unique2 = (array) => { var res = []; var sortedArray = array.concat().sort(); var pre; // pre存储着前一项的值 for (var i = 0, len = sortedArray.length; i < len; i++) { // 假如是第一个元素或者者相邻的元素不相同 if (!i || pre !== sortedArray[i]) { res.push(sortedArray[i]) } pre = sortedArray[i]; } return res; }
3. 利用filter
const unique3 = (arr) => { return arr.filter((item, index, array) => { return arr.indexOf(item) === index; // 此处可以保证是第一次出现的 }) } const unique4 = (arr) => { return arr.concat().sort().filter((item, index, array) => { return !index || item != array[index - 1]; }) }
4. 利用map键值对
const unique5 = (array) => { var obj = {}; return array.filter(function(item, index, array){ return obj.hasOwnProperty(item) ? false : (obj[item] = true) }) } // 缺陷在于对于[1, '1', 2, '2']这种会判断失误,但是可以通过优化来处理
5. Set
const unique6 = (array) => { return [...new Set(array)]; }
找出缺少的数组项
一个数组length = 99,里面的数组项是1~100的值,且无重复,找出缺少的那一个值
const fn = arr => { const sum = (1 + 100) * 50; let sum1 = 0; for(let num of arr) { sum1 += num; } return sum - sum1; // 利用求和来求得缺少的那个值 } const fn1 = arr => { let res = arr[0]; for(let i = 1; i < arr.length; i++) { res = res ^ arr[i]; } for(let i = 1; i <= 100; i++) { res = res ^ i; } // 利用异或者运算来求 return res; } // 创立hash表,初始值都为0,遍历数组,出现的数字将hash表中的值改为1,再遍历一遍hash表,找出值为0的就是缺少的值
假如length = 98,找出缺少的两个
// hash表