这道题是给一个数组,表示一个排列。求比当前排列大的下一个排列。如果没有则返回最小排列。
这道题需要找规律:
无论是对降序序列按照升序序列排序还是交换两个数,都可以在原数组上进行,因此空间复杂度为 O(1),时间复杂度为 O(n^2)。当然,还可以使用二分查找的思想加快(2)中第二步的速度。
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
lens = len(nums)
for i in range(lens-2, -1, -1): # 从后往前遍历找降序子序列
if nums[i] < nums[i+1]:
# 1、将降序的 [i+1, lens-1] 按照升序排列
j, cnt = i + 1, 0
while cnt < (lens - i - 1) // 2:
nums[j], nums[lens-1-cnt] = nums[lens-1-cnt], nums[j]
j += 1
cnt += 1
# 2、在升序的 [i+1, lens-1] 中找到第一个比 nums[i] 大的数字,交换它们
for k in range(i+1, lens):
if nums[k] > nums[i]:
nums[i], nums[k] = nums[k], nums[i]
return
else: # 肯定是降序
nums.reverse()
return
寻找峰值。给一个数组,峰值元素是指其值大于左右相邻值的元素,峰值可能有多个,找到其中一个峰值元素对应索引。假设数组前后均为负无穷。
首先,数组前后均为负无穷可以保证峰值元素一定存在。这道题可以使用二分查找的思想:
high = mid - 1
;low = mid + 1
;因为要比较 nums[mid] 的相邻左右两个元素,因此需要注意边界。可以对边界单独判断。即如果存在 [6,4,...] 或者 [...,4,5] 这种,则可以直接返回 0 或者 len(nums) - 1,因为数组前后均为负无穷, 6 或者 5 就可以视为峰值。
时间复杂度就是二分查找的复杂度,即 O(log n)。
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
lens = len(nums)
if lens == 1 or nums[0] > nums[1]: return 0 # 边界处理
if nums[-1] > nums[-2]: return lens - 1 # 边界处理
low, high = 0, lens - 1
while low <= high:
mid = low + (high - low) // 2
if nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1]: # 找到峰值元素
return mid
elif nums[mid] < nums[mid-1] and nums[mid] > nums[mid+1]: # 在右侧寻找
high = mid - 1
else: # 在左侧寻找
low = mid + 1