js数组相关的手写题

站长

2022年11月21日 17:24 · 阅读数 14

最近没什么时间写长文，写点简单的javascript基础知识吧，数组相关的手写面试题，希望大家都能拿到自己满意的offer。

数组扁平化的6种方式

数组扁平化就是将[1,[2,[3,[4,5]]]] => [1,2,3,4,5]

通过递归实现

function flatArray(arr) {
    if(!Array.isArray(arr)) {
        return null;
    }
    let res = [];
    arr.forEach(item => {
        if(Array.isArray(item)) {
            res = res.concat(flatArray(item));
        } else {
            res.push(item);
        }
    });
    return res;
}
let arr = [1, 2, [3, 4, 5]];
console.log(flatArray(arr))

通过reduce + 递归实现

function flatArray(arr) {
    if(!Array.isArray(arr)) {
        return arr;
    }
    return arr.reduce((pre, cur) => {
        return pre.concat(Array.isArray(cur) ? flatArray(cur) : cur);
    }, []);
}
let arr = [1, 2, [3, 4, 5]];
console.log(flatArray(arr))

通过展开运算符实现

function flatArray(arr) {
    if(!Array.isArray(arr)) {
        return;
    }
    while(arr.some(item => Array.isArray(item))) {
        arr = [].concat(...arr);
    }
    return arr;
}
let arr = [1, 2, [3, 4, 5]];
console.log(flatArray(arr))

通过toString实现，但是里面的值会被转成字符

function flatArray(arr) {
    return arr.toString().split(',').map(item => Number(item));
}
let arr = [1, 2, [3, 4, 5]];
console.log(flatArray(arr))

通过数组的flat方法实现

let arr = [1, 2, [3, 4, 5]];
// 参数表示要展开的层级
console.log(arr.flat(Infinity));

通过JSON.stringify + 正则 + JSON.parse实现

function flatArray(arr) {
    return JSON.parse('['+ JSON.stringify(arr).replace(/\[|\]/g, '') + ']');
}
let arr = [1, 2, [3, 4, 5]];
console.log(flatArray(arr))

排序

冒泡排序

时间复杂度O(n2) 稳定

function BubbleSort(arr) {
    if(arr && arr.length <= 1) {
        return arr;
    }
    for(let i=0; i<arr.length-1; i++) {
        for(let j=i+1; j < arr.length; j++) {
            if(arr[i] > arr[j]) {
                let temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

插入排序

事件复杂度O(n2) 稳定

function insertSort(arr) {
    if(arr && arr.length <= 1) {
        return arr;
    }
    for(let i=1; i<arr.length; i++) {
        let current = arr[i];
        let j = i-1;
        for(; j>=0; j--) {
            if(arr[j] > current) {
                arr[j+1] = arr[j]
            }else {
                break;
            }
        }
        arr[j+1] = current;
    }
    return arr;
}

快速排序

时间复杂度O(nlogn) 不稳定

function quickSort(arr) {
    if(arr && arr.length <= 1) {
        return arr;
    }
    let pivot = Math.floor(arr.length/2);
    let left = [], right = [];
    for(let i = 0; i < arr.length; i++) {
        if(i === pivot) continue;
        if(arr[i] < arr[pivot]) {
            left.push(arr[i]);
        }else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(arr[pivot], quickSort(right));
}

V8里面的sort排序实际上用的是插入排序和快速排序的结合，当长度小于等于10使用插入排序，大于10使用三路快排