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

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

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

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

刷題順序按專題來做，這部分是關(guān)于數(shù)組的，所用語言主要為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.

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

你可以假設(shè)數(shù)組中無重復(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

解題過程

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

最終代碼實(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)，說明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é)果通過了，但不得不說代碼寫的很啰嗦，但就是這個啰嗦的代碼也是一步一步調(diào)試，了解計算機(jī)每一步怎么走才勉強(qiáng)寫出來的，因此編程之路真是路漫漫啊。這里要說明的問題就是，知道計算機(jī)每一步是怎么運(yùn)行的，也就是說養(yǎng)成一種面向計算機(jī)編程的思想，下面就我遇到的問題來記錄參考一下（不具有代表性，面向新手向）。

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

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

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

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

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

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

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

如有不足，歡迎指正。