Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
- * solution1: 遍历
- ```python3
- # -*- coding:utf-8 -*-
- class Solution:
- # array 二维列表
- def Find(self, target, array):
- # write code here
- rows = len(array) - 1
- cols = len(array[0]) - 1
- i = rows
- j = 0
- while i >= 0 and j <= cols:
- if target > array[i][j]:
- j += 1
- elif target < array[i][j]:
- i -= 1
- else:
- return True
- return False
- ```
- * solution2: 二分法
- ```python3
- # -*- coding:utf-8 -*-
- class Solution:
- # array 二维列表
- def Find(self, target, array):
- # write code here
- for i in range(len(array)):
- if len(array[i]) == 0:
- return False
- n = len(array[i])
- if target < array[i][0]:
- return False
- elif target >= array[i][0] and target <= array[i][n-1]:
- lo = 0
- hi = n-1
- mid = 0
- while lo <= hi:
- mid = int((lo + hi)/2)
- if array[i][mid] < target:
- lo = mid + 1
- elif array[i][mid] > target:
- hi = mid - 1
- else:
- return True
- return False
- ```
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement