我正在解決一個問題（leetcode 35）。我的代碼在運行代碼結果中被接受，但是當我提交它時回傳錯誤的答案。我真的不明白我的答案有什么問題。
給定一個排序陣列和一個目標值，如果找到目標，則回傳索引。如果不是，則回傳按順序插入的索引。
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: 0
下面是我的代碼。請幫助我知道錯誤在哪里。提前致謝
/**
* @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;
}
}
};
提交詳情
Input: [1,3,5,6]
2
Output: undefined
Expected: 1
uj5u.com熱心網友回復：
這是因為您錯過了找不到目標編號的情況。在這些情況下，您需要回傳可以在輸入陣列中插入目標數字的索引，同時陣列保持排序。
這是您的 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
};
您最初設定guess為0. 當您進行二分搜索時，如果找到target，只需回傳mid當前最小值和最大值之間的中點。
但是如果nums[mid]小于target你可以確定target至少需要插入，mid 1因為nums[mid]需要target在陣列的左側才能保持排序。
另一方面，如果nums[mid] > target，則target必須將nums[mid]所有內容向右推，并在 處占據元素的索引nums[mid]。所以，在這種情況下，我們設定guess = mid.
最后我們回傳guess。那是因為我們在陣列中沒有目標。
這是一個可以說更優雅但更難閱讀的解決方案：
/**
* @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
};
如果您已經理解了前面的解決方案，請仔細閱讀并嘗試了解它是如何作業的。
另請注意，為避免溢位，您需要使用 進行mid計算left IntergerDivide(right - left)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422783.html
標籤：