LeetCode加热器二进制搜索解(w递归)优化

Question

我在做LeetCode加热器的问题。

问题：https://leetcode.com/problems/heaters/

凛冬将至!您在比赛期间的第一项工作是设计一个固定的暖气半径的标准加热器来温暖所有的房子。现在，给你房子和加热器的位置，在一条水平线上，找出加热器的最小半径，这样所有的房子都可以被这些加热器覆盖。因此，您的输入将分别为房屋和加热器的位置，您的预期输出将是最小半径的加热器标准。

示例输入

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

我编写的解决方案被leetcode所接受，但并不是最优的。

运行时: 656毫秒，超过39.02%的JavaScript在线提交加热器。内存使用:48.2MB，不到12.20%的JavaScript在线提交加热器。

我的解决方案和评论

function findClosest (house, heaters) {
// if only one heater in array of heaters, subtract it with house number to get the difference and return it 
if (heaters.length === 1) return Math.abs(house - heaters[0]) 
  const middleIndex =  Math.floor((heaters.length - 1)/2)
  // if middle heater is equal to house, heater exist on that house number, difference would be zero
  if (house === heaters[middleIndex]) return 0 
  // heater on the leftside and rightside of the middle Heater, if leftside and rightside does not contain any elements (undefinned) then middle would be the left and right most element
  const left = heaters[middleIndex - 1] || heaters[middleIndex] 
  const right = heaters[middleIndex + 1] || heaters[middleIndex]
  // if the left side heater location is greater than current house location, we need to move to left
  if (left > house) { 
   return findClosest(house, heaters.slice(0, middleIndex+1))
  }
    // if the right side heater is less than current house, we need to move to right
  if (house>right) {  
    return findClosest(house, heaters.slice(middleIndex + 1, heaters.length))
  }
 // finding diff b/w left, right and middle index and returning the ones with lease distance
  const middleDiff = Math.abs(house-heaters[middleIndex])
  const leftDiff = house - left 
  const rightDiff = right - house 
  return Math.min(middleDiff, leftDiff, rightDiff)
}


function findRadius  (houses, heater) {
  let maxIndex = 0
  houses.sort((a,b) => a-b)
  heater.sort((a,b) => a-b)
  for (let i=0; i<houses.length; i++) {
    const currentIndex = findClosest(houses[i], heater)
    if (currentIndex > maxIndex) maxIndex = currentIndex // if the current returned distance is the highest, set that as maxIndex
  }
  return maxIndex
}

有人能帮我优化一下吗？

Answer 1

性能这里可以做的主要优化是，在对排序的房子进行迭代时，在测试它们的距离时，一个接一个地沿着加热器前进。只有当房子和下一个加热器之间的差小于房子和当前加热器之间的差时，才能增加加热器指数。这样，每当一个加热器被测试，如果它与当前的房子之间的距离变得太大，该加热器永远不会再测试。

例如，当迭代5个房屋和5个加热器时，算法所使用的每个集合的持久性指示符可能如下所示：

Indicies being examined:
houses heaters
0      0
1      0
2      0
2      1   // at this point, heater 1 is found to be closer to house 2 than heater 0
2      2   // heater 2 is found to be closer to house 2 than heater 1
3      2
4      2
4      3
4      4
5      4
5      5

就是这样。当然，在每一次迭代中，检查加热器和房子之间的距离差，并调用Math.max对该差值和当前距离记录，以获得新的距离记录。

这种方法降低了计算复杂度，从O(n log m) (每栋房子的二进制搜索)到O(n + m)。

function findRadius(houses, heaters) {
    houses.sort((a, b) => a - b);
    heaters.sort((a, b) => a - b);
    // Persistent variable of the current closest heater to the house being iterated over
    let closestHeater = heaters[0];
    // and its index
    let closestHeaterIndex = 0;
    // Current record of needed heater radius
    let requiredRadius = 0;

    for (let i = 0, len = houses.length; i < len; i++) {
        let lastDiff = Math.abs(houses[i] - closestHeater);
        // If we aren't at the end of the heater array,
        // test the next heater to see if we need to increment the heater index:
        while (heaters[closestHeaterIndex + 1]) {
            const nextDiff = Math.abs(heaters[closestHeaterIndex + 1] - houses[i]);
            if (nextDiff > lastDiff) break;
            // This heater is closer to houses[i] than the current one in closestHeater
            lastDiff = nextDiff;
            closestHeaterIndex++;
            closestHeater = heaters[closestHeaterIndex];
        }
        requiredRadius = Math.max(requiredRadius, lastDiff);
    }
    return requiredRadius;
}

结果(屏幕截图)：

运行时: 88毫秒，超过98.89%的JavaScript在线提交加热器。内存使用:42.6MB，不到5.56%的JavaScript在线提交加热器。

关于您的代码的其他几个注意事项：

如果性能有问题，则保存数组长度(除了这些竞赛外，很少是这样)，您可以将数组的当前长度保存在变量中的for循环中，以保存一些计算，就像我上面所做的那样：

for (let i = 0, len = houses.length; i < len; i++) {

分支是昂贵的逻辑分支，比如if和else，但是请记住，它们通常比大多数其他操作慢得多：

作为一个普遍的经验法则，分支比直线代码慢(在所有CPU上，以及在所有编程语言上)。-jmrk V8开发者

如果您有很多分支，您的代码可能不会像您希望的那样快。如果性能确实是个问题的话，在可能的情况下减少它们。

带大括号的块创建环境或环境记录，这些环境记录是标识符到其变量名称的内部映射。如果您严格遵循规范，那么这样的块会导致执行更多的操作。我不确定这是否是现代引擎的问题，或者他们是否可以完全优化它，但如果{和}s只包含一条语句，可能会让事情变得稍微快一些。(但另一方面，去掉大括号可能会使代码读起来有点困难.)

使用表示变量名称，将函数定义为

function findRadius  (houses, heater) {

但heater是一堆加热器；乍一看，heater.sort((a,b) => a-b)让我感到困惑。最好把集合命名为复数。