Leetcode#31 Next Permutation

type
status
date
slug
summary
tags
category
icon
password
给定一个数组,假设其在一个字典顺序中,找到字典顺序的下一位。如果其是字典顺序的最后一位,则给出字典顺序的第一位。
Example:
12345 → 12354
2152351 → 2152513
54321 → 12345

思路

字典为 dic ,可以得到:dic[n] < dic [n+1]
记为 记为 ,相邻的两个元素,可能存在前N位相同的项(N可以为0),我们将前N项去掉。得到
  1. 由于是递增顺序,显而易见: [0] < [0] 。
  1. 由于 的下一项是 ,所以 [1:] 的所有元素无法排列出比现有更大的组合。 [1:] 为递减排列(即能排列出的最大值)。
    1. 同样的道理, 的上一项是 ,所以 [1:] 的所有元素无法排列出比现有更小的组合。 [1:] 为递增排列。
      如果能排列出来,那与“ 的下一项是 ”相冲突
  1. 对于 [0] 和 [0] ,除了已经知道的 [0] < [0] 。还有另外一个规律: [0] 为 所有元素中 [0] 的下一项。(依然是因为 的下一项就是
所以,整体的思路是:
  1. 先从数组右端往左端查找,找到第一个不满足递减的位置。即,当前位置p,比右边小。右边是递减。
  1. 在右边的数组中,从左往右查找,找到最后一个大于nums[p]值的nums[t],交换两者的值,此时nums[p:]依然是一个递减的数组。
  1. 对nums[p:]进行逆序排列,nums[p:]变成递增。
代码:
Loading...

© XGFan 2012-2025