Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
484 views
in Technique[技术] by (71.8m points)

前端面试算法题,选马问题,面试没成功。请问我写的有什么问题,希望各位指点点

第一题:选马问题

题目描述:

有两组马 A 和 B,每一组都有若干匹马。假设所有的马跑的速度都是匀速, 请从两组马中选出跑步速度最接近的两匹马。输入数组 A 和 B,其中 A[i]和 B[j]分别是 A 组第 i 匹和 B 组第 j 匹的速度。输出速度差最小的两匹马之间的速度差值。

例如 A = { 1, 3, 5, 7, 10 }, B = { 2, 3, 6, 9 }, 则输出为 0。

输入:

第一行第 1 个数为 A 组的马的数量 n,后面有 n 个数表示每匹马的速度。

第二行第 1 个数为 B 组的马的数量 m,后面有 m 个数表示每匹马的速度。

每行数字用空格分割。

马的速度为大于 0 小于 2147483647 的整数

输出

输出最小值

样例输入

5 1 7 5 3 10

4 2 9 6 3

样例输出

0

提示

要求程序时间和空间复杂度尽可能低。暴力O(mn)的方法会视为错误

样例程序

function select(A, B) {

// A = [5, 1, 7, 5, 3, 10]

// B = [4, 2, 9, 6, 3]

实现算法

return answer;

}

我的答案

function select(A, B) {
    let arrA = A;
    let arrB = B;
    let resultCompared = [];
    arrA = new Set(A);
    arrB = new Set(B);
    let flagCompared = false;
    arrA.forEach((item, index)=>{
        if(arrB.has(item)){
            // console.log('邮箱等');
            resultCompared = 0;
            // break;
            flagCompared = true;
        }
    });

    if(flagCompared) {
        return resultCompared;
    } else {
        arrA = Array.from(arrA);
        arrB = Array.from(arrB);
        arrA.forEach((itemA, indexA)=>{
            arrB.forEach((itemB, indexB)=>{
                // console.log('indexA+indexB === ', indexA*arrB.length+indexB);
                let resultAB = itemB - itemA;
                if(resultAB < 0) resultAB = resultAB * -1
                resultCompared[indexA*arrB.length+indexB] = resultAB;
            })
        })

        resultCompared = Array.from(new Set(resultCompared));
        let min = 0;
        resultCompared.forEach((item, index)=> {
            if(index === 0) {
                min = item
            } else {
                if(min>item) min = item;
            }
        })
        
        return min;
    }
}

// let A = [5, 1, 10, 1, 10];
// let B = [4, 2, 9, 6, 8];

let A = [5, 1, 7, 5, 3, 10];
let B = [4, 2, 9, 6, 3];
let result = select(A, B);

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

一个想法:
遍历两个数组,得到一个新数组:

const comArr = []
arrA.forEach(i => comArr[i] = 'a')
arrB.forEach(i => {
    if (comArr[i] === 'a') return 0
    else comArr[i] = 'b'
})

如果没有相同速度的马,就得到了一个 [,a,b,a,b,b,,,b,a,,,,a] 的数组
然后根据 entries 遍历一次找最小间距,超过已知最小值还可以跳过


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

2.1m questions

2.1m answers

60 comments

56.6k users

...