常见数组面试题

都是血的教训啊，为什么没早点刷点面试题......

数组扁平化

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表