面试题解答

[EdwardZZZ]

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。 示例 1:

输入：

nums = [1,3,1]
k = 1
输出：0 

解释：
所有数对如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。 

提示:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2. 

const smallestDistancePair = (nums, k) => [].concat(...nums.map((_, i, __, [n1, ..._nums] = nums.slice(i)) => _nums.map((n2) => Math.abs(n1 - n2)))).sort()[k - 1];

[EdwardZZZ]

合并两个排完序的数组，合并后也是同样排序

const arr1 = [1, 3, 5, 7, 9];
const arr2 = [2, 4, 6, 8, 10];

以一个为基准，另一个指针累加

let n = 0;
const newArr = [];

label: for (let i = 0; i < arr1.length; i++) {
    const num1 = arr1[i];
    while (n < arr2.length) {
        const num2 = arr2[n];

        newArr.push(num1 < num2 ? num1 : num2);

        if (num1 < num2) {
            if (i === arr1.length - 1) {
                newArr.push(...arr2.slice(n));
            }
            break;
        }

        if (n++ === arr2.length) {
            newArr.push(...arr1.slice(i));
            break label;
        }
    }
}

console.log(newArr.join(','));

取第一个进行对比

const newArr = [];

while (arr1.length || arr2.length) {
    if (!arr1.length) {
        newArr.push(...arr2);
        break;
    }

    if (!arr2.length) {
        newArr.push(...arr1);
        break;
    }

    newArr.push((arr1[0] > arr2[0] ? arr2 : arr1).shift());
}

console.log(newArr.join(','));

[EdwardZZZ]

两个数组，找到长数组中包含短数组所有的元素的最短子数组，无顺序要求

const arr1 = [7, 5, 9, 0, 2, 1, 3, 5, 7, 9, 1, 1, 5, 8, 8, 9, 7];
const arr2 = [1, 5, 9];

固定长度解法

const hitArr = arr2.map((i) => {
    const arr = [];

    arr1.forEach((j, idx) => {
        if (i === j) arr.push(idx);
    });

    return arr;
});

let minDis = arr1.length;
let smallArr = [];

for (const num1 of hitArr[0]) {
    for (const num2 of hitArr[1]) {
        for (const num3 of hitArr[2]) {
            const numArr = [num1, num2, num3];
            const dis = Math.max(...numArr) - Math.min(...numArr);

            if (dis < minDis) {
                minDis = dis;
                smallArr = numArr;
            }
        }
    }
}

不固定长度解法

class Accumulator {
    constructor(data) {
        this.data = data;
        this.idxArr = Array(this.data.length).fill(0);
    }

    iterator(oneCB, arrCB) {
        while (true) {
            const arrResult = this.idxArr.map((i, idx) => {
                const n = this.data[idx][i];

                if (typeof oneCB === 'function') oneCB(n);

                return n;
            });

            if (typeof arrCB === 'function') arrCB(arrResult);

            if (this.plusPrev(this.data.length - 1)) break;
        }
    }

    plusPrev(digits) {
        this.idxArr[digits]++;

        if (this.idxArr[digits] === this.data[digits].length) {
            this.idxArr[digits] = 0;

            return digits === 0 ? true : this.plusPrev(digits - 1)
        }

        return false;
    }
}

function fn(arr1, arr2) {
    const hitArr = arr2.map((i) => arr1.reduce((prev, j, idx) => {
        if (i === j) prev.push(idx);
        return prev;
    }, []));

    const accumulator = new Accumulator(hitArr);

    let minDis = arr1.length;
    let minArr = [];

    let minNum = arr1.length;
    let maxNum = 0;

    accumulator.iterator((n) => {
        if (n > maxNum) maxNum = n;
        if (n < minNum) minNum = n;
    }, (nArr) => {
        // 可直接取 nArr 数组中最大值最小值进行计算，效率略低  const [min, max] = getMinMax(arr)
        if (maxNum - minNum < minDis) {
            minDis = maxNum - minNum;
            minArr = [minNum, maxNum];
        }

        minNum = arr1.length;
        maxNum = 0;
    });

    return minArr;
}

console.log(fn(arr1, arr2));

[EdwardZZZ]

获取最大最小值

function getMinMax() {
    return arr.reduce((prev, curr, idx) => {
        if (idx === 0) return [curr, curr];

        let [min, max] = prev;

        if (min > curr) min = curr;
        if (max < curr) max = curr;

        return [min, max];
    }, []);
}

[EdwardZZZ]

合并 n 个排完序的数组，合并后也是同样排序

const arr1 = [1, 3, 5, 7, 9];
const arr2 = [2, 4, 6, 8, 10];
const arr3 = [2, 5, 6, 9, 10, 11];

const list = [arr1, arr2, arr3];

function mergeTwoArray(arr1, arr2) {
    const newArr = [];

    let i = 0;
    let j = 0;
    while (i < arr1.length || j < arr2.length) {
        if (i === arr1.length) {
            newArr.push(...arr2.slice(j));
            break;
        }

        if (j === arr2.length) {
            newArr.push(...arr1.slice(i));
            break;
        }

        newArr.push(arr1[i] > arr2[j] ? arr2[j++] : arr1[i++]);
    }

    return newArr;
}

function mergeListArray(list) {
    if (list.length === 0) return [];
    if (list.length === 1) return list[0];
    if (list.length === 2) return mergeTwoArray(...list);

    const midNum = list.length >> 1;

    return mergeTwoArray(mergeListArray(list.slice(0, midNum)), mergeListArray(list.slice(midNum, list.length)));
}

console.log(mergeListArray(list));