都是血的教训啊，为什么没早点刷点面试题......
数组扁平化
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表
更好的办法是将各个数组项归位，详细代码下班后再写。
