SHARE
TWEET

Untitled

a guest Apr 26th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
  2.  
  3. * solution1: 遍历
  4. ```python3
  5. # -*- coding:utf-8 -*-
  6. class Solution:
  7.     # array 二维列表
  8.     def Find(self, target, array):
  9.         # write code here
  10.         rows = len(array) - 1
  11.         cols = len(array[0]) - 1
  12.         i = rows
  13.         j = 0
  14.         while i >= 0 and j <= cols:
  15.             if target > array[i][j]:
  16.                 j += 1
  17.             elif target < array[i][j]:
  18.                 i -= 1
  19.             else:
  20.                 return True
  21.         return False
  22. ```
  23.  
  24. * solution2: 二分法
  25. ```python3
  26. # -*- coding:utf-8 -*-
  27. class Solution:
  28.     # array 二维列表
  29.     def Find(self, target, array):
  30.         # write code here
  31.         for i in range(len(array)):
  32.             if len(array[i]) == 0:
  33.                 return False
  34.            
  35.             n = len(array[i])
  36.             if target < array[i][0]:
  37.                 return False
  38.             elif target >= array[i][0] and target <= array[i][n-1]:
  39.                 lo = 0
  40.                 hi = n-1
  41.                 mid = 0
  42.                 while lo <= hi:
  43.                     mid = int((lo + hi)/2)
  44.                     if array[i][mid] < target:
  45.                         lo = mid + 1
  46.                     elif array[i][mid] > target:
  47.                         hi = mid - 1
  48.                     else:
  49.                         return True
  50.         return False
  51.                    
  52. ```
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top