本周题目难度级别'Easy',由于学习了一段时间Python了,所以以后'Easy'级别的题目全部用Python来写
题目: 本周题目和上周的算法题很像,也是给一个升序的集合和一个数字target,然后这次让你找出target的位置(即升序的集合没有重复的数字),如果集合中没有target,则返回插入target的位置(按升序排列后的位置)
思路:这个思路和上次其实差不多,也很简单,这次就用二分法了:
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0;
right = len(nums)-1;
//如果比组合的第一个小(剪枝)
if target <= nums[left]: return left;
//如果比组合的最后一个大(剪枝)
if target > nums[right]: return right+1;
//二分法开始查找
while (left <= right):
mid = (left + right) >> 1;
if nums[mid] < target:left = mid + 1;
//(剪枝)
if target <= nums[left]: return left;
elif nums[mid] > target:right = mid -1;
//(剪枝)
if target > nums[right]: return right+1;
else:
return mid;
return left;
尽管效率较高,但用时依旧比较长,Python开发的应用要普及应该还要等一段时间,每个语言都有自己的应用场景,不过用Python写算法的人明显的比用C的人多多了。。。