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

Python描述 LeetCode 81. 搜索旋轉排序數組 II

編輯:Python

Python描述 LeetCode 81. 搜索旋轉排序數組 II

大家好,我是亓官劼(qí guān jié ),在【亓官劼】公眾號、CSDN、GitHub、B站等平台分享一些技術博文,主要包括前端開發、python後端開發、小程序開發、數據結構與算法、docker、Linux常用運維、NLP等相關技術博文,時光荏苒,未來可期,加油~

如果喜歡博主的文章可以關注博主的個人公眾號【亓官劼】(qí guān jié),裡面的文章更全更新更快。如果有需要找博主的話可以在公眾號後台留言,我會盡快回復消息.


本文原創為【亓官劼】(qí guān jié ),請大家支持原創,部分平台一直在惡意盜取博主的文章!!! 全部文章請關注微信公眾號【亓官劼】。

題目

已知存在一個按非降序排列的整數數組 nums ,數組中的值不必互不相同。

在傳遞給函數之前,nums 在預先未知的某個下標 k0 <= k < nums.length)上進行了 旋轉 ,使數組變為 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下標 從 0 開始 計數)。例如, [0,1,2,4,4,4,5,6,6,7] 在下標 5 處經旋轉後可能變為 [4,5,6,6,7,0,1,2,4,4]

給你 旋轉後 的數組 nums 和一個整數 target ,請你編寫一個函數來判斷給定的目標值是否存在於數組中。如果 nums 中存在這個目標值 target ,則返回 true ,否則返回 false

你必須盡可能減少整個操作步驟。

示例 1:

輸入:nums = [2,5,6,0,0,1,2], target = 0
輸出:true

示例 2:

輸入:nums = [2,5,6,0,0,1,2], target = 3
輸出:false

提示:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • 題目數據保證 nums 在預先未知的某個下標上進行了旋轉
  • -104 <= target <= 104

進階:

  • 這是 搜索旋轉排序數組 的延伸題目,本題中的 nums 可能包含重復元素。
  • 這會影響到程序的時間復雜度嗎?會有怎樣的影響,為什麼?

Python描述

分成兩個有序序列,然後二分

class Solution:
def search(self, nums: List[int], target: int) -> bool:
idx, n = 0, len(nums)
# 找第一個逆序的位置
while idx < n-1:
if nums[idx] > nums[idx+1]:
break
idx += 1
# 在兩段升序序列中二分查找target
l, r = 0, idx
while l <= r:
mid = l + r>> 1
if nums[mid] == target:
return True
elif nums[mid] < target:
l = mid + 1
else:
r = mid - 1
l, r = idx+1, n-1
while l <= r:
mid = l + r>> 1
if nums[mid] == target:
return True
elif nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return False

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