程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

Leetcode查找(Python和java實現)

編輯:Python

這裡寫目錄標題

    • 1. 搜索范圍 【Search for a Range】
      • Python
    • 2. 搜索插入位置【Search Insert Position】
      • Python
    • 3. 搜索一個二維矩陣【Search a 2D Matrix】
      • Python

1. 搜索范圍 【Search for a Range】

  • 給定一個排序的整數數組,找出給定目標值的開始和結束位置。
  • 你的算法的運行時間復雜度必須是O(logn)的數量級。
  • 如果在數組中沒有找到目標值,返回[-1, -1]。
  • 例如,給定[5, 7, 7, 8, 8, 10]和目標值8,返回[3, 4] 。

分析:已經排好序了,用二分查找最為合適

Python

def search_range(arr, low, high, key):
out = [-1, -1]
mid = (low+high) // 2
if low == high & key != arr[low]:
return [-1, -1]
if key == arr[mid]:
for i in range(mid, high): # range()左閉右開
if key == arr[i]:
out[1] = i
j = mid
while arr[j] == key:
out[0] = j
j = j - 1
return out
elif key < arr[mid]:
temp_high = mid
return search_range(arr, low=low, high=temp_high, key=key)
else:
temp_low = mid + 1
return search_range(arr, low=temp_low, high=high, key=key)
if __name__ == '__main__':
list1 = [5, 7, 7, 8, 8, 10, 10]
print(search_range(list1, low=0, high=len(list1), key=10))

2. 搜索插入位置【Search Insert Position】

給定一個排序的數組和一個目標值,如果找到了目標,則返回索引。如果沒有,則返回索引 如果按順序插入,則返回其所在的索引。你可以假設數組中沒有重復的東西

Python

方法一:循環遍歷,這裡不再贅述。
方法二:先排序,然後返回插入的值的 index

def searchInsert(nums, target):
if target not in nums:
nums.append(target) # 末尾追加
nums.sort() # 排序
return nums.index(target) # 返回索引

方法三:二叉搜索(推薦)

def search_insert(nums, low, high, key):
if low == high:
return low
mid = (high + low) // 2
if nums[mid] < key:
temp_low = mid + 1
return search_insert(nums, low=temp_low, high=high, key=key)
elif nums[mid] > key:
temp_high = mid
return search_insert(nums, low=low, high=temp_high, key=key)
else: # nums[mid] == key
return mid
if __name__ == '__main__':
list1 = [1, 3, 5, 7, 8, 10]
print(search_insert(list1, low=0, high=len(list1), key=9))

3. 搜索一個二維矩陣【Search a 2D Matrix】

寫一個有效的算法,在一個m×n的矩陣中搜索一個值。這個矩陣有以下特性。

  • 每行的整數從左到右排序。
  • 每一行的第一個整數大於前一行的最後一個整數。

例如,以下矩陣。

[[1,3,5,7],
[10,11,16,20],
[23,30,34,50]]

Python

解法一:使用numpy將二維數組變為一維數組,然後使用二叉搜索

def search_2dm(matrix_flatten, low, high, target):
if low >= high and matrix_flatten[low] != target: # 沒有key值
return False
mid = (high + low) // 2
if matrix_flatten[mid] > target:
temp_high = mid
return search_2dm(matrix_flatten, low=low, high=temp_high, target=target)
elif matrix_flatten[mid] < target:
temp_low = mid + 1
return search_2dm(matrix_flatten, low=temp_low, high=high, target=target)
else: # matrix_flatten[mid] == key
return True
if __name__ == '__main__':
list1 = [[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]]
list1 = np.array(list1).flatten()
print(search_2dm(list1, low=0, high=len(list1), target=2))

方法二

def search_matrix(matrix, target):
matrix = np.array(matrix)
row = matrix.shape[0] # 獲取行號
column = matrix.shape[1] # 獲取列數
first = 0
last = row * column
while first < last:
mid = first + (last-first)//2
value = matrix[(mid // column), (mid % column)]
if value == target:
return True
elif value < target:
first = mid + 1
else:
last = mid
return False
if __name__ == '__main__':
list1 = [[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]]
print(search_matrix(list1, 70))

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved