算法题目5：挑选电脑

题目：小特最近要开学了，他打算入学前买一台笔记本电脑。小特看中了戴尔和微软的超薄本，他打算 先找两个品牌价格最接近的型号比较一下性能。他已经在电商网站上找到了两个品牌各个型号的 价格, 请你写程序帮助他找到价格差最小的两款!
输入:
第一行第 1 个数为 戴尔电脑型号的数量 n，接着有 n 个数表示每个型号的价格。
第二行第 1 个数为 微软电脑型号的数量 m，接着有m个数表示每个型号的价格。 每行数字用空格分割。
电脑价格为大于 0 小于 2147483647 的整数
输出:
输出价格差最小的两款电脑的下标，用空格分开
样例输入:
5 3998 4698 6698 8898 7798
4 2068 5688 10198 5288
样例输出:
1 3(价格最接近的是 4698 和 5288，下标分别为 1 和 3)
提示:
暴力 O(mn)的方法会视为错误

思路：二路归并

解法：

function generateNumbers(n){
    let arr = []
    for (let i = 0; i < n; i++) {
        let num = parseInt(Math.random() * 100000000)
        arr.push(num)
    }
    return arr
}

function cmpPrice(a, b) {
    return a.price - b.price
}

// 查找arr1 和 arr2 最相近的两个数的下标
function findNearest(arr1, arr2) {
    let x = [], y = []
    for (let i = 0; i < arr1.length; i++) {
        x.push({price:arr1[i], index:i})
    }
    for (let i = 0; i < arr2.length; i++) {
        y.push({price:arr2[i], index:i})
    }
    // 按价格排序 复杂度O(mlgm)+O(nlgn)
    x.sort(cmpPrice)
    y.sort(cmpPrice)

    let a = x.shift()
    let b = y.shift()
    let delta = 2147483647 // 历史最小差值
    let idx1 = 0 // 历史最小差值对应的arr1.index
    let idx2 = 0 // 历史最小差值对应的arr2.index

    // 两路归并, 复杂度O(m+n)
    while (true) {
        let d = Math.abs(a.price - b.price)
        if (d == 0) { // 两个值相等，这是最小的差值了，直接返回结果
            return [a.index, b.index]
        }
        // 如果当前的差值比历史最小差值还小，那么就更新下
        if (d < delta) {
            idx1 = a.index
            idx2 = b.index
            delta = d
        }
        // 两个队列都空了，返回
        if (x.length == 0 && y.length == 0) {
            return [idx1, idx2]
        }
        if (x.length == 0) {        // x空了，那么从y取一个
            b = y.shift()
        }else if (y.length == 0) {  // y空了，那么从x取一个
            a = x.shift()
        }else if (a.price < b.price) {  // 谁小从谁那取
            a = x.shift()
        }else {
            b = y.shift()
        }
    }

    // 总复杂度O(mlgm)+O(nlgn) + O(m+n) 即 O(mlgm) 假设m>n
}

// 查找arr1 和 arr2 最相近的两个数的下标
// 穷举解法，用来验证答案
function exhaustive(arr1, arr2) {
    let delta = 2147483647
    let idx1 = 0
    let idx2 = 0
    for (let i = 0; i < arr1.length; i++) {
        for (let j = 0; j < arr2.length; j++) {
            let d = Math.abs(arr1[i] - arr2[j])
            if (d < delta) {
                idx1 = i
                idx2 = j
                delta = d
            }
        }
    }
    return [idx1, idx2]
}

function solve() {
    let arr1 = generateNumbers(10)
    let arr2 = generateNumbers(15)
    console.log("arr1 =",arr1)
    console.log("arr2 =",arr2)

    let result = findNearest(arr1, arr2)
    console.log('当前算法结果:',result, '左:',arr1[result[0]], '右:', arr2[result[1]], '差值', Math.abs(arr1[result[0]]-arr2[result[1]]))

    let result2 = exhaustive(arr1, arr2)
    console.log('穷举算法结果:',result2, '左:',arr1[result2[0]], '右:', arr2[result2[1]], '差值', Math.abs(arr1[result2[0]]-arr2[result2[1]]))
}

solve()