本文主要是介绍LeetCode35. Search Insert Position-python(easy) 二分法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目来源:
https://leetcode.com/problems/search-insert-position/description/
题目分析:
给定一个排好序的数组和一个target,如果target在数组里面,那么返回他的位置,否者返回他应该插入哪个位置。
本题我们可以考虑用二分法查找,如果没有找到,那么和first和last位置的数比较一下就可以得到答案。我们需要记住这道题的思路。
class Solution:def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""first=0;last=len(nums)-1while (first<last):mid=(first+last+1)//2 %python3中,//表示取整除运算符,返回商的整数部分,/表示正常的除法,可得到小数,可得到整数if(nums[mid]==target):return midelif(nums[mid]>target):last=mid-1else:first=mid+1 %按照我的理解,循环过后,要么找到了元素,要么此时last和first是紧挨着的状态。if (nums[last]<target ):return (last+1)if(nums[last]>=target):return lastif(target<nums[first]):return firstreturn first+1
除此以外,看到有人是这样做的
class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int""" return len([x for x in nums if x<target])
直接从头开始找,然后进行插入或者返回所在的位置。
下面再介绍一个python 有趣的排序模块:bisect(用于已经排序好的列表)
首先看一下模块的结构,这个时候我们可以使用dir()函数。使用dir()函数可以查看对像内所有属于及方法,在python中任何东西都是对像,一种数据类型,一个模块等,都有自己的属性和方法,除了常用方法外,其它的你不需要全部记住它,交给dir()函数就好了,dir()函数操作方法很简单,只需要把你想要查询和对像添写到( )括号中就可以使用了。比如:
import bisect
dir(bisect)
print(dir(bisect))
此时返回:
['__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'bisect', 'bisect_left
前面五个属性大家感兴趣可以打出来看看数值,这里就不介绍了。
先说明的是,使用这个模块的函数前先确保操作的列表是已排序的。
先看看 insort 函数:
其插入的结果是不会影响原有的排序。
再看看 bisect 函数:
其目的在于查找该数值将会插入的位置并返回,而不会插入。
接着看 bisect_left 和 bisect_right 函数,该函数用入处理将会插入重复数值的情况,返回将会插入的位置:
其对应的插入函数是 insort_left 和 insort_right :
可见,单纯看其结果的话,两个函数的操作结果是一样的,其实插入的位置不同而已。
因此,本题也可以直接返回:bisect.bisect_left(nums,target)
这篇关于LeetCode35. Search Insert Position-python(easy) 二分法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!