35. Search Insert Position

置顶

Created At : 2021-04-07 23:57

Count:543 Views 👀 :

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

Example 1:

**Input:** nums = [1,3,5,6], target = 5
**Output:** 2

Example 2:

**Input:** nums = [1,3,5,6], target = 2
**Output:** 1

Example 3:

**Input:** nums = [1,3,5,6], target = 7
**Output:** 4

Constraints:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order.
-10^4 <= target <= 10^4

这道题基本没有什么难度，实在不理解为啥还是 Medium 难度的，完完全全的应该是 Easy 啊（貌似现在已经改为 Easy 类了），三行代码搞定的题，只需要遍历一遍原数组，若当前数字大于或等于目标值，则返回当前坐标，如果遍历结束了，说明目标值比数组中任何一个数都要大，则返回数组长度n即可，代码如下：

解法一：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] >= target) return i;
        }
        return nums.size();
    }
};

当然，我们还可以用二分搜索法来优化时间复杂度，而且个人认为这种方法应该是面试官们想要考察的算法吧，属于博主之前的总结帖 LeetCode Binary Search Summary 二分搜索法小结中第二类 - 查找不小于目标值的数，参见代码如下：

解法二：

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

Github 同步地址：

https://github.com/grandyang/leetcode/issues/35

类似题目：

First Bad Version

参考资料：

https://leetcode.com/problems/search-insert-position/

https://leetcode.com/problems/search-insert-position/discuss/15372/Simple-Java-solution

https://leetcode.com/problems/search-insert-position/discuss/15080/My-8-line-Java-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️.