Find the breakpoint from the end which breaks the non-increasing sequence. [1, 3, 5, 4, 2] -> 3
Traverse from end in right part and find the first element greater than breakpoint. [1, 4, 5, 3, 2] -> 34互换
Reverse the right part. [1, 4, 2, 3, 5]
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 如果第一部分用 for i in range(len(nums) -1, 0, -1)写法，会导致单元素的list为空. 且费时
i = len(nums) - 1
while i > 0:
if nums[i-1] < nums[i]:
break
i -= 1
pivot = i - 1
if pivot == -1:
nums.reverse()
return
for j in range(len(nums) - 1, pivot, -1):
if nums[j] > nums[pivot]:
nums[j], nums[pivot] = nums[pivot], nums[j]
break
# python list 可以这样局部更新
nums[pivot+1:] = reversed(nums[pivot+1:])
时间复杂度：O(n)
空间复杂度：O(1)
follow up-多步翻转法
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
in-place
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
lens = len(nums)
if k == lens:
return
k = k % lens
self.reverse(nums, 0, lens-1)
self.reverse(nums, 0, k - 1)
self.reverse(nums, k, lens-1)
def reverse(self, nums, l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
剑指Offer 45: 把数组排成最小的数
import functools
class Solution:
def PrintMinNumber(self, numbers):
if not numbers:
return ""
num = list(map(str, numbers))
cmp = lambda a, b: 1 if a + b > b + a else -1
num = sorted(num, key=functools.cmp_to_key(cmp))
return ''.join(num)
class Solution:
def nextGreaterElement(self, n: int) -> int:
str_num = str(n)
if len(str_num) <= 1:
return -1
i = len(str_num) - 1
while i > 0:
if str_num[i-1] >= str_num[i]:
i -= 1
else:
break
if i == 0:
return -1
pivot = i - 1
j = len(str_num) - 1
str_num_list = list(str_num)
while j >= i - 1:
if str_num[j] > str_num[pivot]:
str_num_list[j], str_num_list[pivot] = str_num_list[pivot], str_num_list[j]
break
else:
j -= 1
str_num_list[pivot+1:] = reversed(str_num_list[pivot+1:])
res = int(''.join(str_num_list))
if res > 2**31 - 1:
return -1
return res