output errato dei riscaldatori leetcode

Question

Stavo facendo la domanda del riscaldatore del leetcode.

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

Su 23/30 input su invio, ricevo un output errato ma non riesco a capire perché,

23 ° ingresso

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

L'output previsto è: 161834419ma il mio output attuale è181367746

Ecco il mio codice

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))

Cosa sto facendo

• Trovare il raggio sinistro e destro più vicino da casa
• Quale è più vicino viene confrontato con il raggio massimo corrente, se è maggiore di quello diventa il raggio massimo corrente

Qualcuno può aiutarmi a trovare errori nel mio algoritmo?

Answer 1

Devi controllare anche l'elemento centrale. Questa è la condizione che manca nel tuo caso.

Il codice aggiornato sarebbe:

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
}