第一题：选马问题

题目描述：

有两组马 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);

一个想法：
遍历两个数组，得到一个新数组：

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 遍历一次找最小间距，超过已知最小值还可以跳过

题主好，我是《了不起的JavaScript工程师》的作者亚里士朱德。
思考了一下，觉得可以用排序+双指针实现，如有不对之处欢迎指正。

1.先分别使用sort函数对数组进行排序。
V8采用Timsort算法
时间复杂度为: O(nlogn)
空间复杂度为: O(n)

2.然后用双指针进行遍历比对，找到最小值。
循环数组复杂度为: O(n)
空间复杂度为: O(1)

所以总体复杂度 max{O(mlogm),O(nlogn)}，小于O(m*n)。

function select(A, B) {
  let answer = Infinity;
  A.sort((a, b) => a - b);
  B.sort((a, b) => a - b);
  let idxA = 0;
  let idxB = 0;
  while(idxA<A.length && idxB<B.length) {
    answer = Math.min(answer, Math.abs(A[idxA] - B[idxB]))
    if(answer===0) break;
    A[idxA] < B[idxB] ? idxA++ : idxB++;
  }
  return answer;
}
let A = [5, 1, 7, 5, 3, 10]
let B = [4, 2, 9, 6, 3]
select(A, B)