Repository navigation
LeetCode: 31. 下一个排列 #76
Description
思路：
找几个例子分析一下就可以得知
- 从最后一个开始遍历，找到不是降序的第一个数字的索引，即为index
- 从最后一个开始遍历，找到第一个比nums[index]大的第一个数字
- 交换两个数字
- 从index + 1开始，重新排序一下即可。
class Solution {
public:
void nextPermutation(vector<int>& nums) {
next_permutation(nums.begin(), nums.end());
}
template<typename BidiIt>
bool next_permutation(BidiIt first, BidiIt last) {
const auto rfirst = reverse_iterator<BidiIt>(last);
const auto rlast = reverse_iterator<BidiIt>(first);
auto pivot = next(rfirst);
while (pivot != rlast and !(*pivot < *prev(pivot)))
++pivot;
if (pivot == rlast) {
reverse(rfirst, rlast);
return false;
}
auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot));
swap(*change, *pivot);
reverse(rfirst, pivot);
return true;
}
};class Solution:
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
length = len(nums)
if length == 1:
return
if length == 2:
nums[0], nums[1] = nums[1], nums[0]
return
index = length - 1
last = nums[length - 1]
# 遍历第一遍
for i in range(length - 2, -1, -1):
index = i
if last > nums[i]:
break
last = nums[index]
secondIndex = length
# 遍历第二遍
for i in range(length - 1, -1, -1):
secondIndex = i
if nums[i] > nums[index]:
break
if index == secondIndex:
nums.sort()
return
print(index, secondIndex)
nums[index], nums[secondIndex] = nums[secondIndex], nums[index]
y = nums[index + 1: length]
y.sort()
nums[index + 1: length] = y
Activity
[-]d[/-][+]LeetCode: 31. 下一个排列[/+]