资讯专栏INFORMATION COLUMN

【Leetcode刷题】第 35 题:Search Insert Position 搜索插入位置——

haobowd / 2076人阅读

摘要:如果目标值不存在于数组中,返回它将会被按顺序插入的位置。因此需要关注这些测试用例,在单机上逐个测试成功后再提交。因为题目中只要求返回索引,并不要求插到数组中,所以应该说又简化了一些,是一道简单题目。争取在下一篇给出优化解法。

「 Leetcode刷题 」系列,仅为刷题过程中对于算法和编程的思考与记录,如果对你有帮助欢迎点赞收藏。博主也在探索刷题过程中,记录的一些知识点可能很小白,因此主要是想做一个记录。文中的不足请多担待。

刷题顺序按专题来做,这部分是关于数组的,所用语言主要为python3。每题将分为解题篇总结篇两篇,一篇是博主自己的解法,一篇是学习大家解法后的总结。


数组部分 题目

英文:

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:

输入: [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


解题过程

对于这道题,我一开始的想法是先解决目标值在数组中的情况,然后解决目标值不在数组中的情况。想法也很简单,用for循环遍历数组查找是否相等;如果目标值不存在数组中,则通过比较大小,把它放到合适的位置。

最终代码实现如下:

class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """

        for i in range(len(nums)):
            if target == nums[i]:
                print(i)
                return i

        # 直接跳出for循环,说明target不存在于nums中
        if target > nums[i]:
            print(i+1)
            return i+1
        elif target < nums[0]:
            print(0)
            return 0
        else:
            for i in range(len(nums)):
                if target > nums[i] and target < nums[i+1]:
                    print(i+1)
                    return i+1

提交结果如下:

虽然结果通过了,但不得不说代码写的很啰嗦,但就是这个啰嗦的代码也是一步一步调试,了解计算机每一步怎么走才勉强写出来的,因此编程之路真是路漫漫啊。这里要说明的问题就是,知道计算机每一步是怎么运行的,也就是说养成一种面向计算机编程的思想,下面就我遇到的问题来记录参考一下(不具有代表性,面向新手向)。

1、在数组范围这里for i in range(len(nums))这条语句,在 python 中会依次遍历数组,直到所有的数组元素遍历完,然后退出循环,所以这里写成range(len(nums)),当然有更简单的方法,我们之后说。

2、当for循环结束时未返回任何值,程序直接跳出for循环,执行下一步语句,说明target不存在于nums中,因此我在下面用了if的判断语句对边界条件进行判断。

3、目标值不在数组中的情况,必须排除掉之前的情况才可,if target > nums[i] and target < nums[i+1]这句语句一开始我直接放到了整个数组中重新执行,那么就会出现数组下标越界的情况,因为它包含了上面的情况,这时候对于测试用例子输入: [1,3,5,6], 7 输出: 4这种情况就会有问题。对于我们人来说,进行重新判断的想法是很自然的,但在计算机中机就不能直接进行判断,而会导致错误的结果,所以不能想当然的写下语句,而是学会怎么向计算机一样思考。

4、在 python 中不同于 C 语言中连续的if else,用了elif来代替。

5、print语句仅仅是打印值,而不会返回任何值,题目里要求的是要输出一个值,所以需要return

6、最后,对于 leetcode 刷题有一些注意的地方。我们看这道题的测试用例,其实很有考究。总共 4 条,第 1 条是目标值在数组中的情况,其余 3 条是目标值不在数组中,第 2 条是目标值应该被放到数组中间,第 3 和 4 条是放到数组两边。因此需要关注这些测试用例,在单机上逐个测试成功后再提交。因为题目中只要求返回索引,并不要求插到数组中,所以应该说又简化了一些,是一道简单题目。


关于 Leetcode 刷题初体验就到这里了,需要学习的真是太多了。争取在下一篇给出优化解法。


如有不足,欢迎指正。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/44944.html

相关文章

  • [Leetcode] Search Insert Position 搜索插入位置

    摘要:二分搜索法复杂度时间空间思路这是最典型的二分搜索法了。这题中,我们返回就行了,如果返回,要注意的情况。代码条件是找到了在左边在右边 Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the inde...

    JeOam 评论0 收藏0
  • leetcode35 Search Insert Position

    题目要求:在一个有序的数组中,找到一个目标值,返回该值得下标。若没有找到该值,则返回该值顺序插入的下标例如,[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0 public int searchInsert(int[] nums, int target) { int index=0; ...

    harriszh 评论0 收藏0
  • Leetcode[35] Search Insert Position

    Leetcode[35] Search Insert Position Given a sorted array and a target value, return the index if thetarget is found. If not, return the index where it would be if it wereinserted in order.You may assu...

    jasperyang 评论0 收藏0
  • LeetCode 攻略 - 2019 年 7 月下半月汇总(100 攻略)

    摘要:月下半旬攻略道题,目前已攻略题。目前简单难度攻略已经到题,所以后面会调整自己,在刷算法与数据结构的同时,攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题,目前已攻略 100 题。 一 目录 不折腾的前端,和咸鱼有什么区别...

    tain335 评论0 收藏0
  • LeetCode 之 JavaScript 解答239 —— 滑动窗口最大值(Sliding W

    摘要:你只可以看到在滑动窗口内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。算法思路暴力破解法用两个指针,分别指向窗口的起始位置和终止位置,然后遍历窗口中的数据,求出最大值向前移动两个指针,然后操作,直到遍历数据完成位置。 Time:2019/4/16Title: Sliding Window MaximumDifficulty: DifficultyAuthor: 小鹿 题目...

    spacewander 评论0 收藏0

发表评论

0条评论

haobowd

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<