Leetcode【31、162】
Leetcode【31、162】
echobingo
发布于 2019-10-09 15:29:02
发布于 2019-10-09 15:29:02
问题描述：【Math】31. Next Permutation
解题思路：
这道题是给一个数组，表示一个排列。求比当前排列大的下一个排列。如果没有则返回最小排列。
这道题需要找规律：
- （1）对于 [6,1,2,3] 这种，很明显只需要交换最后两个数字即可。
- （2）对于 [2,3,2,1] 和 [10,6,5,7,3] 这种，需要两步操作：第一步，从后往前遍历数组，找到降序序列（分别是 [3,2,1] 和 [7,3]），并记录第一个不符合降序序列的数字 num （分别是 2 和 5），将降序序列按照升序排列（分别是 [1,2,3] 和 [3,7]）；第二步，在刚刚排好的升序序列中，找到第一个比数字 num （分别是 2 和 5）大的数字，进行交换即可（分别是 [3,1,2,2] 和 [10,6,7,3,5]）。
- （3）对于 [6,5,4,3,2,1] 这种，在从后往前遍历数组时，找到了完整的降序序列，因此没有比该排列大的下一排列了。这时只需要 nums.reverse()，返回最小排列即可。
- （4）注意观察 （1）、（2）可以合并成（2）这一种情况。
无论是对降序序列按照升序序列排序还是交换两个数，都可以在原数组上进行，因此空间复杂度为 O(1)，时间复杂度为 O(n^2)。当然，还可以使用二分查找的思想加快（2）中第二步的速度。
Python3 实现：
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问题描述：【Binary Search】162. Find Peak Element
解题思路：
寻找峰值。给一个数组，峰值元素是指其值大于左右相邻值的元素，峰值可能有多个，找到其中一个峰值元素对应索引。假设数组前后均为负无穷。
首先，数组前后均为负无穷可以保证峰值元素一定存在。这道题可以使用二分查找的思想：
- （1）对于 nums = [1,2,3,2,1]，如果 nums[mid] 比前后两个元素都要大，则 mid 就应该是答案；
- （2）对于 nums = [1,4,3,2,1]，如果 nums[mid] 比左边的小、比右边的大，则说明峰值元素应该在左区间，
high = mid - 1； - （3）对于 nums = [1,2,3,4,1]，如果 nums[mid] 比左边的大、比右边的小，则说明峰值元素应该在右区间，
low = mid + 1； - （4）对于 nums = [5,4,3,4,5]，如果 nums[mid] 比前后两个元素都要小，则将这种情况随便归为（2）、（3）其中一种即可。因为数组前后均为负无穷可以保证峰值元素一定存在。
因为要比较 nums[mid] 的相邻左右两个元素，因此需要注意边界。可以对边界单独判断。即如果存在 [6,4,...] 或者 [...,4,5] 这种，则可以直接返回 0 或者 len(nums) - 1，因为数组前后均为负无穷， 6 或者 5 就可以视为峰值。
时间复杂度就是二分查找的复杂度，即 O(log n)。
Python3 实现：
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本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.10.09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录