python题目编程答案高中信息技术python题目不会做怎么办
下载地址 https://share.weiyun.com/OvviwGnZ
资料目录
Python练习集100题
100道Python面试题
Python100经典练习题
Python经典题目100道题
Python题库(已收录100道真题）
Python100例视频讲解课程
菜鸟教程Python教程100例
130道python练习题，涵盖基础内容的方方面面
Python考试题复习知识点试卷试题
PYTHON测试题和答案
python第一阶段考试题
Python经典面试题和答案解析
python期末考试复习试卷
python习题集大全（附答案解析）
老男孩Python全栈7期练习题（面试真题模拟）
尚观python第一阶段考试（面试真题模拟）
《Python程序设计基础与应用》习题答案
《Python快速编程入门》——课后题答案
Python编程基础张健 , 张良均课后习题及答案
Python程序设计基础及实践（慕课版）郭炜习题答案
Python程序设计基础习题答案与分析
python基础试题(含答案)
举例 搜索二维矩阵
题目要求
已知一个矩阵，有以下特点：
• 每行的元素从左到右是升序的
• 每列的元素从上到下是升序的
示例如下
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
请编写一个高效的算法搜索目标值target
思路分析
每行数据和每列数据都是升序的，但行与行之间并没有升序关系，第二行的数据并不是都比第一行大。因此，搜索数据时，必须从第一行开始进行搜索。
搜索某一行时，由于数据有序，因此可以轻松的找到最小值和最大值
• 如果最小值比target大，可以确定整个矩阵里都没有目标值
• 如果最大值比target小，说明这一行里肯定不存在目标值。
• 如果target>= min and target <= max，就在这一行里进行查找，关键之处在于，如果这一行里没有找到目标值，还要继续去下一行里查找么？答案是肯定的，比如你想找5，第一行里没有找到，但是第二行里却可以找得到，而且，你无法跳过第一行直接查找第二行，因为第一行里可能有5
前面的三点分析，已经让搜索算法非常高效了，接下来要考虑如何高效的在一行数据里查找目标值，由于每一行数据是有序的，因此可以使用二分查找法，二分查找法已经非常高效了，但是由于每一列从上到下也是升序的，因此，可以对二分查找法稍稍做一点改变，就可以让整个的查找速度更快。
如果二分查找法在找不到目标值时，返回第一个比目标值大的元素的索引，那么，这个索引就可以作为下一次查找时结束位置的边界，比如搜索9，对第一行使用二分查找法搜索时没有找到目标值，但是找到了第一个比9大的元素11，索引为3，由于每一列都是升序的，所以搜索第二行时，不需要搜索整行，只需要搜索0到2这个索引范围就可以了。通过对二分查找法小做修改，就使得之后的每一行搜索范围得以缩小，效率更高。
示例代码
def binary_search(lst, start, end, target):
"""
如果目标值存在,则返回目标值索引和下一个位置
如果目标值不存在,则返回第一个比目标值大的元素的索引
如果最大值比目标值还小,则返回整行的长度
:param lst:
:param start:
:param end:
:param target:
:return:
"""
if start > end:
return -1, start + 1
middle = (start + end)//2
if lst[middle] == target:
return middle, middle + 1
elif lst[middle] > target:
return binary_search(lst, start, middle-1, target)
else:
return binary_search(lst, middle+1, end, target)
def search_matrix(matrix, target):
if len(matrix) == 0:
return 0
if len(matrix[0]) == 0:
return False
end_index = len(matrix[0]) -1
for lst in matrix:
min_value = lst[0]
max_value = lst[-1]
if target < min_value:
return False # 此处可以直接返回False
if target > max_value:
continue # 目标值比这一行最大值还大,去下一行查找
target_index, end_index = binary_search(lst, 0, end_index, target)
end_index -= 1 # 下一次搜索时结束的位置
if target_index >= 0:
return True
return False
if __name__ == '__main__':
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 6))
print(search_matrix(matrix, 16))
print(search_matrix(matrix, 20))
print(search_matrix([[1]], 1))
|