035 Search Insert Position[E]

03-04

1 題目描述

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.

難度：Easy

2 題目樣例

Example 1:Input: [1,3,5,6], 5Output: 2Example 2:Input: [1,3,5,6], 2Output: 1Example 3:Input: [1,3,5,6], 7Output: 4Example 1:Input: [1,3,5,6], 0Output: 0

3 題意分析

給定一個排序的數組，查找指定元素，如果在數組中返回下標否則返回應該插入的下標。

4 思路分析

又是在考lower_bound和upper_bound咯。

代碼如下

class Solution {public: int searchInsert(vector<int>& nums, int target) { auto it = lower_bound(nums.begin(), nums.end(), target); if(it!=nums.end() && *it == target) return it - nums.begin(); else return upper_bound(nums.begin(),nums.end(), target) - nums.begin(); }};

整體時間複雜度 $O(lgn)$ ，空間複雜度 $O(1)$

5 後記

水題。