首页 > 代码库 > leetcode 【 Search Insert Position 】python 实现
leetcode 【 Search Insert Position 】python 实现
题目：
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.
Here are few examples.[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0
代码：oj测试通过 Runtime: 52 ms
1 class Solution: 2 # @param A, a list of integers 3 # @param target, an integer to be inserted 4 # @return integer 5 def search(self, A, start, end, target): 6 # search stop case I 7 if start == end: 8 if start == 0: 9 return [ 0,1 ][ A[0]<target ]10 if A[start] == target:11 return start12 else:13 return [start,start+1][A[start]<target]14 # search stop case II15 if start+1 == end:16 if A[start] >= target:17 return start18 elif A[start] < target and A[end] >= target :19 return end20 else:21 return end+122 23 mid = (start+end)/224 # search stop case III25 if A[mid] == target:26 return mid27 if A[mid] > target:28 return self.search(A, start, mid-1, target)29 if A[mid] < target:30 return self.search(A, mid+1, end, target)31 32 def searchInsert(self, A, target):33 # zero length case34 if len(A) == 0:35 return 036 # binary search37 start = 038 end = len(A)-139 return self.search(A, start, end, target)
思路：
二分查找经典题。
采用迭代方式时：
1. 考虑start==end的情况（一个元素）和start+1==end的情况（两个元素），作为迭代终止的两种case。
2. 当元素数量大于3时作为一般的case处理，二分查找。
3. 根据题意要求进行判断条件。
4. 第一次提交没有AC ，原因是在处理start==end的case时候，竟然值考虑了0和len(A)的边界情况，没有考虑一般情况，陷入了思维的陷阱。
后面又写了一版非递归的代码：oj测试通过 Runtime: 63 ms
1 class Solution: 2 # @param A, a list of integers 3 # @param target, an integer to be inserted 4 # @return integer 5 def searchInsert(self, A, target): 6 # zero length case 7 if len(A) == 0 : 8 return 0 9 # binary search10 start = 011 end = len(A)-112 while start <= end :13 if start == end:14 if start == 0:15 return [0,1][A[0]<target]16 if A[start] == target:17 return start18 else:19 return [start,start+1][A[start]<target]20 if start+1 == end:21 if A[start] >= target:22 return start23 elif A[start] < target and A[end] >= target:24 return end25 else:26 return end+127 mid = (start+end)/228 if A[mid] == target:29 return mid30 elif A[mid] > target:31 end = mid - 132 else:33 start = mid + 1
思路跟非递归差不太多。
个人感觉判断stop case的代码虽然逻辑上比较清晰（剩一个元素或者两个元素或者直接找到了target），但是并不是很简洁。后续再不断改进。
leetcode 【 Search Insert Position 】python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。