leetcode chauffe sortie incorrecte

Question

Je faisais une question de chauffage leetcode.

Question: https://leetcode.com/problems/heaters/

Sur l'entrée 23/30 lors de la soumission, j'obtiens une sortie incorrecte mais je ne peux pas comprendre pourquoi,

23ème entrée

[282475249,622650073,984943658,144108930,470211272,101027544,457850878,458777923]
[823564440,115438165,784484492,74243042,114807987,137522503,441282327,16531729,823378840,143542612]

La sortie attendue est: 161834419mais ma sortie actuelle est181367746

Voici mon code

const a = [282475249,622650073,984943658,144108930,470211272,101027544,457850878,458777923]
const b = [823564440,115438165,784484492,74243042,114807987,137522503,441282327,16531729,823378840,143542612]

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))
  }
    // 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 and right index and returing the ones with lease distance
  const leftDiff = house - left 
  const rightDiff = right - house 
  if (leftDiff < rightDiff) return leftDiff 
  else return rightDiff
}


const 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
}


console.log(findRadius(a, b))

Que suis-je en train de faire

• Trouver les rayons gauche et droit les plus proches de la maison
• Celui qui est le plus proche est comparé au rayon maximum actuel, s'il est supérieur à cela devient le rayon maximum actuel

Quelqu'un peut-il m'aider à trouver une erreur dans mon algo?

Answer 1

Vous devez également vérifier l'élément du milieu. C'est la condition qui manque dans votre cas.

Le code mis à jour serait:

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 and right index and returing 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
}