Estoy resolviendo un problema (leetcode 35). Mi código fue aceptado en el resultado del código de ejecución, pero cuando lo envío, devuelve una respuesta incorrecta. Realmente no entiendo qué es lo que está mal en mi respuesta.
Dada una matriz ordenada y un valor objetivo, devuelve el índice si se encuentra el objetivo. Si no, devuelve el índice donde estaría si se insertara en orden.
Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0a continuación está mi código. Por favor, ayúdenme a saber dónde está el error. Gracias de antemano
/** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function(nums, target) { var min = 0; var max = nums.length - 1; var guess; while(min <= max) { guess = Math.floor((max + min) / 2); if (nums[guess] === target) { return guess; } else if (nums[guess] < target) { min = guess + 1; } else { max = guess - 1; } } };detalles de envío
Input: [1,3,5,6] 2 Output: undefined Expected: 1Es porque te falta el caso en el que no se encuentra el número objetivo. En esos casos, debe devolver el índice donde se puede insertar el número de destino en la matriz de entrada mientras la matriz permanece ordenada.
Aquí hay una versión correcta de su código JS:
/** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function(nums, target) { var min = 0; var max = nums.length - 1; let guess = 0 while(min <= max) { const mid = Math.floor((max + min) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] < target) { min = mid + 1; guess = mid+1 } else { max = mid - 1 guess = mid; } } return guess }; Inicialmente configuraste guess en 0 . Mientras realiza una búsqueda binaria, si encuentra target , simplemente devuelva mid , que es el punto medio entre el mínimo y el máximo actuales.
Pero si nums[mid] es más pequeño que target , puede estar seguro de que el target debe insertarse al menos en mid+1 porque nums[mid] debe estar a la izquierda del target para que la matriz permanezca ordenada.
Por otro lado, si nums[mid] > target , target debe empujar nums[mid] y todo a su derecha a la derecha y ocupar el índice del elemento en nums[mid] . Entonces, en este caso, establecemos guess = mid .
Al final devolvemos guess . Eso es porque no tenemos el objetivo en la matriz.
Aquí hay una solución posiblemente más elegante pero un poco más difícil de leer:
/** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function(nums, target) { let left = 0; let right = nums.length while(left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] < target) { left = mid + 1; } else { right = mid guess = mid; } } return left };Si ha entendido la solución anterior, revise esta y trate de entender cómo funciona.
También tenga en cuenta que para evitar el desbordamiento, debe calcular mid con left + IntergerDivide(right - left) .