专栏首页木又AI帮打卡群2刷题总结1002——搜索插入位置

打卡群2刷题总结1002——搜索插入位置


leetcode第35题:搜索插入位置

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


【题目】

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

你可以假设数组中无重复元素。

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

【思路】

1、暴力解法:遍历数组,查找元素。

2、二分查找:题目类型为找到第一个大于等于target的元素,返回其位置。

二分查找一般使用通用代码:

i, j = 0, len(nums) - 1
while i <= j:
 mid = (i + j) // 2
 if nums[mid] > target:
  j = mid - 1
 else:
  i = mid + 1
return i
# 循环结束后,得到的结果是:nums[j] <= target < nums[i]
# 解释:只要nums[mid]大于target,j就前移,因此最终nums[j]肯定小于等于target;同理,nums[i]大于target。
# 可以发现,最重要的是nums[mid] > target这个式子中的运算符,以及返回的下标,这两个也是通用代码中必须要根据题目进行修改的部分。
# 当nums[mid] > target,最终结果nums[j] <= target < nums[i]
# 当nums[mid] >= target,最终结果nums[j] < target <= nums[i]

怎么使用呢?1)根据题目,找到自己想要的循环后的结果;比如,找到第一个大于target的元素,结果就应该是num[j] <= target < nums[i]。2)写入模板,根据需要更改运算符及返回值;比如,找到第一个大于target的元素,运算符应该是>,返回的是i。

【代码】

python版本

二分查找

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        
        # 第一个 >= target的元素
        # nums[r] < target <= nums[l]
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] >= target:
                r = mid - 1
            else:
                l = mid + 1
        
        return l

【相似题目】

34. 在排序数组中查找元素的第一个和最后一个位置

解题方法:二分查找

278. 第一个错误的版本

解题方法:二分查找

704. 二分查找

解题方法:二分查找

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群2刷题总结1013——不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    木又AI帮
  • 打卡群2刷题总结1003——搜索旋转排序数组

    https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

    木又AI帮
  • 打卡群刷题总结0721——搜索二维矩阵

    链接:https://leetcode-cn.com/problems/search-a-2d-matrix

    木又AI帮
  • 打卡群刷题总结0807——验证二叉搜索树

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 打卡群刷题总结0805——不同的二叉搜索树

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 打卡群刷题总结0727——搜索旋转排序数组 II

    链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

    木又AI帮
  • 打卡群2刷题总结1001——两数之和 II - 输入有序数组

    https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

    木又AI帮
  • 杭电OJ刷题指南

    说起来刷题,很多大牛都会推荐LeetCode或者牛客网,这两个网站是刷题的好网站。但对新手来说,有一点难度,新手建议先去杭电OJ刷题,这里的题目难度不大,如果你...

    Jasonangel
  • 黑产是如何强刷用户银行卡8.1万元的?

    故事梗概 今年端午节特意动用带薪年假,在家本着远离黑客,远离江湖,舒舒服服和家人享受几天假期,谁知却早已深陷江湖。 6月11日中午叔叔找上门,说自己的银行卡莫名...

    FB客服
  • 力扣 (LeetCode)-对称二叉树,树|刷题打卡

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • Mysql - JOIN 详解

    一个完整的SQL语句中会被拆分成多个子句,子句的执行过程中会产生虚拟表(vt),但是结果只返回最后一张虚拟表。从这个思路出发,我们试着理解一下JOIN查询的执行...

    程序员宝库
  • 数据库MySQL中的JOIN详解

    一个完整的SQL语句中会被拆分成多个子句,子句的执行过程中会产生虚拟表(vt),但是结果只返回最后一张虚拟表。从这个思路出发,我们试着理解一下JOIN查询的执行...

    程序你好
  • 打卡群刷题总结0804——二叉树的中序遍历

    非递归解法,需要使用栈结构,同时使用一个visit数组标识该节点是否访问过其孩子节点。得到visit栈顶元素,判断是否访问过;如果访问过,则val加入到结果中;...

    木又AI帮
  • 打卡群刷题总结1005——跳跃游戏

    链接:https://leetcode-cn.com/problems/jump-game

    木又AI帮
  • 打卡群刷题总结0630——在排序数组中查找元素的第一个和最后一个位置

    链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-s...

    木又AI帮
  • Hadoop学习5--配置本地开发环境(Windows+Eclipse)

    一、导入hadoop插件到eclipse 插件名称:hadoop-eclipse-plugin-2.7.0.jar 我是从网上下载的,还可以自己编译。 放到ec...

    小端
  • 「最全总结」没有公众号和流量渠道,该如何推火自己的小程序?

    蘑菇街小程序, 90 天获得了 300 万新用户;「星巴克用星说」上线仅三个月,便获得几百万用户;腾讯公益 1 元购「小朋友画廊」在朋友圈刷屏,不到一天便获得了...

    知晓君
  • 打卡群刷题总结0825——括号生成

    链接:https://leetcode-cn.com/problems/generate-parentheses

    木又AI帮
  • 回溯算法:复原IP地址

    题目地址:https://leetcode-cn.com/problems/restore-ip-addresses/

    代码随想录

扫码关注云+社区

领取腾讯云代金券