LeeCode每日一题--搜索插入位置

Noya ·

更新时间:2024-09-21

· 749 次阅读

【前言】坚持日更LeeCode刷题系列
不积跬步,无以至千里;不积小流,无以成江海。愿与诸君共勉！

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

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

示例:

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

思路一:如果使用列表内的方法，这题思路很简单，如果target在nums内，则调用index函数返回下标值；如果target不在nums内，则将该元素添加到列表内排序后，用index函数返回其下标值。具体代码如下：

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target in nums:
            return nums.index(target)
        else:
            nums.append(target)
            nums.sort()
            return nums.index(target)

运行结果：
在这里插入图片描述

思路二:通过二分查找的方法进行求解。具体代码如下：

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 0:  #特殊情况单独考虑
            return 0
        elif nums[len(nums)-1] < target: #特殊情况单独考虑
            return len(nums)
        else:
            left = 0
            right = len(nums)-1
            while(left<right):
                mid = (left+right)/2
                if(nums[mid]<target):  #当nums[mid]<target时说明左半部分不存在其解
                    left = mid+1
                else:
                    right = mid
            return left

运行结果：
在这里插入图片描述