LeetCode 刷题 35- 简单 - 搜索插入位置

ベ布小禅

关注

发布于: 刚刚

前言

算法作为极其重要的一点，是大学生毕业找工作的核心竞争力，所以为了不落后与人，开始刷力扣算法题！

第一遍，不求最优解，但求能过！！！

📢 这是我刷第 8/100 道力扣简单题

一、题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

难度：简单

二、实例

示例 1:
输入: nums = [1,3,5,6], target = 5输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7输出: 4示例 4:
输入: nums = [1,3,5,6], target = 0输出: 0示例 5:
输入: nums = [1], target = 0输出: 0

复制代码

三、题目解析

这个题很明显嘛，用二分查找做，限制必须要用 O(logn)的时间复杂度

像我们学会了某种算法，能用就多用，加深理解，也是更优化的代码

不过需要具体分析

如果目标值在数组/列表中，就是正常的二分查找就能做

如果不在，就要细分一下

不过是简单题，我就不多说了，看代码

四、代码

class Solution:    def searchInsert(self, nums: List[int], target: int) -> int:        start = 0  # 初始下标        end = len(nums)-1  # 最大值的下标        while start<=end:            mid = (start+end)//2  # 中间下标            if target>nums[mid]:                start = mid +1            elif target==nums[mid]:                return mid            else:                end = mid-1        return start

复制代码

结语

坚持最重要，每日一题必不可少！

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/2283f501365e34a1070c5bde7】。文章转载请联系作者。

ベ布小禅

关注

还未添加个人签名 2021.04.06 加入

平平无奇一萌新，默默无闻学IT，我是布小禅，一个网络专业却对编程及其感兴趣的小白！目前在学python和Java，都很浅显，平时爱写点学习笔记。IT技术交流群：1039347613 也可以联系本人企鹅：2228660752 v：Smly0413

发布

暂无评论

创作场景

LeetCode 刷题 35- 简单 - 搜索插入位置

前言

一、题目描述

二、实例

三、题目解析

四、代码

结语

ベ布小禅

评论