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

Python description leetcode 81 Search rotation sort array II

編輯:Python

Python describe LeetCode 81. Search rotation sort array II

Hello everyone , I'm Qi Guanjie (qí guān jié ), stay 【 Qi Guanjie 】 official account 、CSDN、GitHub、B Share some technical blog posts on the website and other platforms , It mainly includes front-end development 、python The backend development 、 Applet development 、 Data structure and algorithm 、docker、Linux Common operation and maintenance 、NLP And other related technical blog , Time flies , Future period , come on. ~

If you love bloggers, you can focus on the bloggers' official account. 【 Qi Guanjie 】(qí guān jié), The articles inside are more complete and updated faster . If you need to find a blogger, you can leave a message at the official account. , I will reply to the message as soon as possible .


This article was originally written as 【 Qi Guanjie 】(qí guān jié ), Please support the original , Some platforms have been stealing blog articles maliciously !!! All articles please pay attention to WeChat official account 【 Qi Guanjie 】.

subject

It is known that there is an array of integers in non descending order nums , The values in the array don't have to be different from each other .

Before passing it to a function ,nums In some unknown subscript k0 <= k < nums.length) On the rotate , Make array [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]( Subscript from 0 Start Count ). for example , [0,1,2,4,4,4,5,6,6,7] In subscript 5 It may turn into [4,5,6,6,7,0,1,2,4,4] .

Here you are. After rotation Array of nums And an integer target , Please write a function to determine whether the given target value exists in the array . If nums There is a target value in target , Then return to true , Otherwise return to false .

You must minimize the whole procedure .

Example 1:

 Input :nums = [2,5,6,0,0,1,2], target = 0
Output :true

Example 2:

 Input :nums = [2,5,6,0,0,1,2], target = 3
Output :false

Tips :

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • Topic data assurance nums Rotated on a previously unknown subscript
  • -104 <= target <= 104

Advanced :

  • This is a Search rotation sort array The extended topic of , In this question nums It may contain repeating elements .
  • Does this affect the time complexity of the program ? What kind of impact will it have , Why? ?

Python describe

Divided into two ordered sequences , Then two points

class Solution:
def search(self, nums: List[int], target: int) -> bool:
idx, n = 0, len(nums)
# Find the first position in reverse order 
while idx < n-1:
if nums[idx] > nums[idx+1]:
break
idx += 1
# Binary search in two ascending sequences 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