daily leetcode - search-insert-position - !

题目地址

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.

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

思路

这道题基本没有什么难度,实在不理解为啥还是 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;
    }
};

本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode


标题: daily leetcode - search-insert-position - !
文章作者: lonuslan
文章链接: https://www.lonuslan.com/articles/2020/02/03/1580711599555.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LonusLan
    评论
    0 评论
avatar

取消