[35. Search Insert Position]
(https://leetcode.cn/problems/search-insert-position/)
- 此題是從一個升序陣列且陣列內元素不重復查找目標值，因此首選二分法
- 二分法前提：
- 有序陣列
- 陣列內元素不重復
- 此題難點是如何確定最終結果的index
- 若 nums[middle] == target ，直接return middle
- 但對于大于和小于這兩種情況，則需找找規律：
- 最終沒有找到target會退出回圈，若target依然大于middle（也就是left和right下標對應值），則left = middle + 1，那么很顯然，return left；但若target小于middle，則right = middle - 1，很顯然依舊return left
- 綜上所述，在最終沒有找到target退出回圈，最終我們應該return的值始終是left
- 那么題目就很簡單了，也就是二分法模板 + return left
- 代碼如下：
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1; //確定最初的查找區間
//左閉右閉
while( left <= right )
{
//防止溢位
int middle = left + ( (right - left) >> 1 );
if( nums[middle] == target )
{
return middle;
}
else if( nums[middle] > target )
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
return left;
}
};
-
時間復雜度：O（logn）
空間復雜度：O（1）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/514100.html
標籤：其他
上一篇：leetcode 219. Contains Duplicate II 存在重復元素 II(簡單)
下一篇：6步搭建一個飛機大戰游戲