leetcode 【 Search Insert Position 】python 实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode 【 Search Insert Position 】python 实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2380字，纯文字阅读大概需要4分钟。
内容图文
题目：
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:
8if start == 0:
9return [ 0,1 ][ A[0]<target ]
10if A[start] == target:
11return start
12else:
13return [start,start+1][A[start]<target]
14# search stop case II15if start+1 == end:
16if A[start] >= target:
17return start
18elif A[start] < target and A[end] >= target :
19return end
20else:
21return end+1
2223 mid = (start+end)/2
24# search stop case III25if A[mid] == target:
26return mid
27if A[mid] > target:
28return self.search(A, start, mid-1, target)
29if A[mid] < target:
30return self.search(A, mid+1, end, target)
3132def searchInsert(self, A, target):
33# zero length case34if len(A) == 0:
35return 0
36# binary search37 start = 0
38 end = len(A)-1
39return 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 :
8return 0
9# binary search10 start = 0
11 end = len(A)-1
12while start <= end :
13if start == end:
14if start == 0:
15return [0,1][A[0]<target]
16if A[start] == target:
17return start
18else:
19return [start,start+1][A[start]<target]
20if start+1 == end:
21if A[start] >= target:
22return start
23elif A[start] < target and A[end] >= target:
24return end
25else:
26return end+1
27 mid = (start+end)/2
28if A[mid] == target:
29return mid
30elif A[mid] > target:
31 end = mid - 1
32else:
33 start = mid + 1
思路跟非递归差不太多。
个人感觉判断stop case的代码虽然逻辑上比较清晰（剩一个元素或者两个元素或者直接找到了target），但是并不是很简洁。后续再不断改进。
原文：http://www.cnblogs.com/xbf9xbf/p/4245711.html
内容总结
以上是互联网集市为您收集整理的leetcode 【 Search Insert Position 】python 实现全部内容，希望文章能够帮你解决leetcode 【 Search Insert Position 】python 实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。