最佳利用

Question

我在做来自leetcode的最佳利用代码

问题链接：https://leetcode.com/discuss/interview-question/373202

问题:给定两个列表a和b，每个元素是一对整数，其中第一个整数表示唯一的id，第二个整数表示一个值。您的任务是从a和元素表单b中找到一个元素，使它们的值之和小于或等于目标值，并尽可能接近目标。返回选定元素的ids列表。如果不可能对，则返回空列表。

为此，我编写了以下算法

let a, b, target
const currentHighest = (array1, array2, target) => {
  const hashMapA = {}
  const hashMapB = {}
  const arr1 = array1.sort((a, b) => {
    hashMapA[[a[1]]] = a[0]
    hashMapA[[b[1]]] = b[0]
    return a[1] - b[1]
  })
  const arr2 = array2.sort((a, b) => {
    hashMapB[[a[1]]] = a[0]
    hashMapB[[b[1]]] = b[0]
    return a[1] - b[1]
  })
  const id = {}
  const currentHighest = {
    difference: Infinity,
    indexes: []
  }
  let i = 0
  const arr2mid = parseInt(arr2.length / 2)
  while (i < arr1.length) {
    const a1 = arr1[i]
    const difference = target - a1[1]
    if (hashMapB.hasOwnProperty(difference)) {
      if (!id.hasOwnProperty(a1[0])) {
        if (currentHighest.difference !== 0) currentHighest.indexes = []
        id[[a1[0]]] = true
        currentHighest.difference = 0
        currentHighest.indexes.push([a1[0], hashMapB[difference]])
      }
    } else {
      let j = 0;
      let itteratorEndpoint = arr2.length
      if (difference > arr2[arr2mid][1]) j = arr2mid
      while (j < itteratorEndpoint && difference > arr2[j][1]) {
        const a2 = arr2[j]
        const difference2 = target - a2[1]
        if (hashMapA.hasOwnProperty(hashMapA[difference2])) {
          if (!id.hasOwnProperty(a2[0])) {
            if (currentHighest.difference !== 0) currentHighest.indexes = []
            id[[hashMapA[difference2]]] = true
            currentHighest.difference = 0
            currentHighest.indexes.push([hashMapA[difference2], a2[0]])
          }
        }
        const actualDifference = target - (a1[1] + a2[1])

        if (actualDifference > -1) {
          if (currentHighest.difference === actualDifference) currentHighest.indexes.push([a1[0], a2[0]])
          if (currentHighest.difference > actualDifference && currentHighest.difference !== 0) {
            currentHighest.difference = actualDifference
            currentHighest.indexes = [
              [a1[0], a2[0]]
            ]
          }
        }
        j++
      }
    }
    i++
  }
  return currentHighest.indexes
}

a = [
  [1, 8],
  [2, 15],
  [3, 9]
]
b = [
  [1, 8],
  [2, 11],
  [3, 12]
]
target = 20

console.log(currentHighest(a, b, target))

My approach

1. 对数组进行排序，并在排序时为A和B创建一个hashMap
2. id对象确保未对特定id进行迭代。
3. 当前索引用于跟踪差异和这些差异的索引。
4. 在排序数组arr1上，我使用while循环开始迭代。
5. 我们检查arr1中当前元素的目标值与值之间的差异，如果hashMapB中存在差异，则将索引存储在currentHighest中，并将差值设置为零。
6. 否则，我们将检查arr2中中点的值。我们使用它来比较arr2中点的值和差值的值，如果差值大于我们可以从中点迭代到差值保持较大的点。
7. 创建difference2，检查hashMap A中是否存在该值，如果存在，它将执行与以前相同的操作
8. 如果没有，我们计算arr1元素和arr2元素之间的差异和迭代，比较它们的值，如果它们的差值恰好小于存储的差值，我们就设置索引，使我们的新的差异。
9. 我们返回currentHighest.indexes

虽然下面的代码确实有效，但我并不认为它是最佳的。有人能帮我，并建议我如何使这段代码进行优化吗？

Answer 1

您的代码接缝量很大，非常复杂。

我不认为有必要对数组进行排序，因为开销并不能保证带来好处。

分配给排序函数中的映射是非常低效率的。排序函数将被调用比数组中的项多很多次。

我会说if (hashMapB.hasOwnProperty(difference)) {是多余的，因为可以假定leetcode环境中的对象在原型链中没有更高的可枚举属性需要担心。因此，if (hashMapB[difference] !== undefined)将具有更高的性能。

长变量名使您的代码难以理解。考虑短名称，并使用常用的缩写，以减少行长度。

JS会自动插入分号，但在许多情况下插入分号的位置并不明显。缺乏经验的JS编码人员应该始终使用分号。经验丰富的程序员知道更容易将他们包括在内。

您不需要用{}来分隔单行语句块，但是在修改代码时，它是未来bug的一个来源，因为添加{}很容易被忽略，而且很难识别。始终分隔所有语句块。if (foo) bar =1和if (foo) { bar = 1 }一样好

您提供的链接不是一个可测试的问题，而是一个leetcode讨论主题。除了在讨论中提出的有限论据外，我没有什么可检验的。有许多问题是，给定的输入集不能回答，编写最优解是不可能的。下面的示例只是一个复杂的O(nm)的强力解决方案，其中n和m是两个输入数组的长度。

示例

将此函数与您的函数进行比较，并假设求和值是有符号整数(而不是无符号整数，因为如果项的值大于和(第3 arg)，则允许跳过内循环)。

该示例返回一个结果，在0.589 S对您的函数25.250 S( your = 1/1,000,000,000秒)

我没有在非常大的数据集上测试它，也没有太深入地寻找一个不那么复杂的解决方案。

为了避免每次发现更大的最大值和时创建一个新数组，我使用一个计数器foundCount作为在result数组中放置新的更紧密索引的索引。函数完成后，我只需将数组的长度设置为已找到的计数，就可以对数组进行调整。

function currentHighest(a, b, max) {
    const lenA = a.length, lenB = b.length, result = [];
    var i = 0, j, foundCount = 0, maxFound = -Infinity;
    while (i < lenA) {
        j = 0;
        const pA = a[i], valA = pA[1];
        while (j < lenB) {
            const pB = b[j], sum = valA + pB[1];
            if (sum <= max && sum >= maxFound) {
                if (sum !== maxFound) { foundCount = 0 }    
                maxFound = sum;
                result[foundCount++] = [pA[0], pB[0]];
            }
            j++;
        }
        i++;
    }
    result.length = foundCount;
    return result;
}