一、复习
-31、下一个排列
我吐,整体思路没问题;但是:
(1)快排问题可太大了,又出错了,居然忘记写range了!!!
找了半天的错误。
(2)里层循环找的是距离要交换的那位数最近的那个数,是记录下下来的index;而不是循环到最后的i,j
33、 搜索旋转排序数组
愈发凌乱,而且还不会啊啊啊啊啊附上今日份糟糕代码
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
if n==1:
if nums[0]==target:
return 0
else:
return -1
lo = 0
hi = n - 1
while (lo < hi):
mid = (lo + hi) // 2
if nums[mid] > nums[lo]:
if nums[lo]<=target <nums[mid]:
hi = mid
while (lo < hi):
mid = (lo + hi) // 2
if target < nums[mid]:
hi = mid
elif nums[mid] < target:
lo = mid + 1
else:
return mid
elif target==nums[mid]:
return mid
else:
lo = mid + 1
else:
if nums[hi]>=target > nums[mid]:
while (lo < hi):
mid = (lo + hi) // 2
if target < nums[mid]:
hi = mid
elif nums[mid] < target:
lo = mid + 1
else:
return mid
elif target==nums[mid]:
return mid
else:
hi = mid
return -1
直接去学昨日答案了我丢!!!!!!!!!!!!!!!!!!!!!!!!!
又看了一边答案,我的感觉就是,要做两次比较:
(1)比较nums[mid]和端点的值,确定mid在哪一段上,进而分而治之
(2)(在具体某段上)比较nums[mid]和target的值,进一步分而治之确定target的范围。
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊终于过了!!!!!!!!
需要注意的点:
(1)第一个比较是nums【mid】和端点比较,而不是target,脑子要清醒。
(2)在进行左右缩小单位的时候,注意左右都-1/+1,根据具体情况确定。
(3)不要忘了在判断中加等号,要不然容易丢掉两端index=0和n-1的情况。
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
lo = 0
hi = n-1
while(lo<=hi):
mid = (lo+hi)//2
if nums[mid]==target:
return mid
if nums[0]<=nums[mid]:
if nums[0]<=target<nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid]<target<=nums[n-1]:
lo = mid+1
else:
hi =mid -1
return -1