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

haobowd 發(fā)布于2019-07-31 11:17 / 2077人閱讀

摘要：如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。因此需要關(guān)注這些測(cè)試用例，在單機(jī)上逐個(gè)測(cè)試成功后再提交。因?yàn)轭}目中只要求返回索引，并不要求插到數(shù)組中，所以應(yīng)該說(shuō)又簡(jiǎn)化了一些，是一道簡(jiǎn)單題目。爭(zhēng)取在下一篇給出優(yōu)化解法。

「 Leetcode刷題」系列，僅為刷題過(guò)程中對(duì)于算法和編程的思考與記錄，如果對(duì)你有幫助歡迎點(diǎn)贊收藏。博主也在探索刷題過(guò)程中，記錄的一些知識(shí)點(diǎn)可能很小白，因此主要是想做一個(gè)記錄。文中的不足請(qǐng)多擔(dān)待。

刷題順序按專題來(lái)做，這部分是關(guān)于數(shù)組的，所用語(yǔ)言主要為python3。每題將分為解題篇和總結(jié)篇兩篇，一篇是博主自己的解法，一篇是學(xué)習(xí)大家解法后的總結(jié)。

數(shù)組部分 題目

英文：

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.

中文：
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

你可以假設(shè)數(shù)組中無(wú)重復(fù)元素。

示例 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

解題過(guò)程

對(duì)于這道題，我一開(kāi)始的想法是先解決目標(biāo)值在數(shù)組中的情況，然后解決目標(biāo)值不在數(shù)組中的情況。想法也很簡(jiǎn)單，用for循環(huán)遍歷數(shù)組查找是否相等；如果目標(biāo)值不存在數(shù)組中，則通過(guò)比較大小，把它放到合適的位置。

最終代碼實(shí)現(xiàn)如下：

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循環(huán)，說(shuō)明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

提交結(jié)果如下：

雖然結(jié)果通過(guò)了，但不得不說(shuō)代碼寫(xiě)的很啰嗦，但就是這個(gè)啰嗦的代碼也是一步一步調(diào)試，了解計(jì)算機(jī)每一步怎么走才勉強(qiáng)寫(xiě)出來(lái)的，因此編程之路真是路漫漫啊。這里要說(shuō)明的問(wèn)題就是，知道計(jì)算機(jī)每一步是怎么運(yùn)行的，也就是說(shuō)養(yǎng)成一種面向計(jì)算機(jī)編程的思想，下面就我遇到的問(wèn)題來(lái)記錄參考一下（不具有代表性，面向新手向）。

1、在數(shù)組范圍這里for i in range(len(nums))這條語(yǔ)句，在 python 中會(huì)依次遍歷數(shù)組，直到所有的數(shù)組元素遍歷完，然后退出循環(huán)，所以這里寫(xiě)成range(len(nums))，當(dāng)然有更簡(jiǎn)單的方法，我們之后說(shuō)。

2、當(dāng)for循環(huán)結(jié)束時(shí)未返回任何值，程序直接跳出for循環(huán)，執(zhí)行下一步語(yǔ)句，說(shuō)明target不存在于nums中，因此我在下面用了if的判斷語(yǔ)句對(duì)邊界條件進(jìn)行判斷。

3、目標(biāo)值不在數(shù)組中的情況，必須排除掉之前的情況才可，if target > nums[i] and target < nums[i+1]這句語(yǔ)句一開(kāi)始我直接放到了整個(gè)數(shù)組中重新執(zhí)行，那么就會(huì)出現(xiàn)數(shù)組下標(biāo)越界的情況，因?yàn)樗松厦娴那闆r，這時(shí)候?qū)τ跍y(cè)試用例子輸入: [1,3,5,6], 7 輸出: 4這種情況就會(huì)有問(wèn)題。對(duì)于我們?nèi)藖?lái)說(shuō)，進(jìn)行重新判斷的想法是很自然的，但在計(jì)算機(jī)中機(jī)就不能直接進(jìn)行判斷，而會(huì)導(dǎo)致錯(cuò)誤的結(jié)果，所以不能想當(dāng)然的寫(xiě)下語(yǔ)句，而是學(xué)會(huì)怎么向計(jì)算機(jī)一樣思考。

4、在 python 中不同于 C 語(yǔ)言中連續(xù)的if else，用了elif來(lái)代替。

5、print語(yǔ)句僅僅是打印值，而不會(huì)返回任何值，題目里要求的是要輸出一個(gè)值，所以需要return。

6、最后，對(duì)于 leetcode 刷題有一些注意的地方。我們看這道題的測(cè)試用例，其實(shí)很有考究。總共 4 條，第 1 條是目標(biāo)值在數(shù)組中的情況，其余 3 條是目標(biāo)值不在數(shù)組中，第 2 條是目標(biāo)值應(yīng)該被放到數(shù)組中間，第 3 和 4 條是放到數(shù)組兩邊。因此需要關(guān)注這些測(cè)試用例，在單機(jī)上逐個(gè)測(cè)試成功后再提交。因?yàn)轭}目中只要求返回索引，并不要求插到數(shù)組中，所以應(yīng)該說(shuō)又簡(jiǎn)化了一些，是一道簡(jiǎn)單題目。

關(guān)于 Leetcode 刷題初體驗(yàn)就到這里了，需要學(xué)習(xí)的真是太多了。爭(zhēng)取在下一篇給出優(yōu)化解法。

如有不足，歡迎指正。