Skip to content

35.search insert position

难度:Easy

刷题内容

原题连接

  • https://leetcode.com/problems/search-insert-position/
  • 内容描述

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.

思路1 **- 时间复杂度: O(lgN)*- 空间复杂度: O(1)***

由于数组是已经排序好的,这就是一个很典型的二分法

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int first = 0,last = nums.size() - 1;
        while(last > (first + 1))
        {
            int medium = (last + first) / 2;
            if(nums[medium] == target)
                return medium;
            else if(nums[medium] < target)
                first = medium;
            else
                last = medium;
        }
        if(target > nums[last])
            return last + 1;
        else if((target < nums[first]) || (target == nums[first]))
            return first;
        else
            return last;
    }
};

思路2 **- 时间复杂度: O(lgN)*- 空间复杂度: O(1)***

其实这个思路也是二分法,只不过c++中已经给我们封装好了lower_bound,我们直接调用即可 代码看上去也简洁很多

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        auto pos = lower_bound(nums.begin(),nums.end(),target);
        return pos - nums.begin();
    }
};


回到顶部