数组排列问题 | YOLOのBLOG

一、下一个排列（中）

题目

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。
必须原地修改，只允许使用额外常数空间。

示例 1：
输入：$nums = [1,2,3]$
输出：$[1,3,2]$

示例 2：
输入：$nums = [3,2,1]$
输出：$[1,2,3]$

示例 3：
输入：$nums = [1,1,5]$
输出：$[1,5,1]$

提示：
$1 <= nums.length <= 100$
$0 <= nums[i] <= 100$

题解

怎么说呢，首先你得读懂题目。
就是按照升序排序，然后依次选取次大的元素进行排序组合。

举个例子，
$[1,2,3]-[1,3,2]-[2,1,3]-[2,3,1]-[3,1,2]-[3,2,1]$
所以$[1,2,3]$下一个排列就是$[1,3,2]$

这道题记住思路，就很容易解决。
1、从右开始遍历，先找出第一个索引$i$，满足$nums[i] < nums[i+1]$，如果不存在，就翻转整个数组；
2、再从右开始遍历，找出第二个索引$j$，满足$nums[j] > nums[i]$；
3、交换$nums[j]$和$nums[i]$；
4、最后翻转$nums[i+1:]$。

比如$nums = [1,2,7,4,3,1]$，下一个排列是什么？
我们找到第一个索引是$nums[1] = 2$；
再找到第二个索引是$nums[4] = 3$；
交换，$nums = [1,3,7,4,2,1]$；
翻转，$nums = [1,3,1,2,4,7]$。

class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    if (nums.size() == 0) {
      return;
    }
    int firstIndex = -1;
    for (int i = nums.size() - 2; i >= 0; i--) {
      if (nums[i] < nums[i + 1]) {
        firstIndex = i;
        break;
      }
    }
    if (firstIndex == -1) {
      reverse(nums.begin(), nums.end());
      return;
    }
    int secondIndex = -1;
    for (int i = nums.size() - 1; i > 0; i--) {
      if (nums[i] > nums[firstIndex]) {
        secondIndex = i;
        break;
      }
    }
    int temp = nums[firstIndex];
    nums[firstIndex] = nums[secondIndex];
    nums[secondIndex] = temp;
    reverse(nums.begin() + firstIndex + 1, nums.end());
  }
};

二、上一个排列（中）

题目

给定一个整数数组来表示排列，按升序找出其上一个排列。

示例 1：
输入：$nums = [1]$
输出：$[1]$

示例 2：
输入：$nums = [1,3,2,3]$
输出：$[1,2,3,3]$

示例 3：
输入：$nums = [1,2,3,4]$
输出：$[4,3,2,1]$

提示：
$1 <= nums.length <= 100$
$0 <= nums[i] <= 100$

题解

跟下一个排列一样，只不过求的是上一个，而不是下一个。

举个例子，
$[1,2,3]-[1,3,2]-[2,1,3]-[2,3,1]-[3,1,2]-[3,2,1]$
所以$[1,3,2]$上一个排列就是$[1,2,3]$

所以只需要根据第一题的代码，只用把遍历里的>换成<即可。
1、从右开始遍历，先找出第一个索引$i$，满足$nums[i] > nums[i+1]$，如果不存在，就翻转整个数组；
2、再从右开始遍历，找出第二个索引$j$，满足$nums[j] < nums[i]$；
3、交换$nums[j]$和$nums[i]$；
4、最后翻转$nums[i+1:]$。

class Solution {
 public:
  void prevPermutation(vector<int>& nums) {
    if (nums.size() == 0) {
      return;
    }
    int firstIndex = -1;
    for (int i = nums.size() - 2; i >= 0; i--) {
      if (nums[i] > nums[i + 1]) {
        firstIndex = i;
        break;
      }
    }
    if (firstIndex == -1) {
      reverse(nums.begin(), nums.end());
      return;
    }
    int secondIndex = -1;
    for (int i = nums.size() - 1; i > 0; i--) {
      if (nums[i] < nums[firstIndex]) {
        secondIndex = i;
        break;
      }
    }
    int temp = nums[firstIndex];
    nums[firstIndex] = nums[secondIndex];
    nums[secondIndex] = temp;
    reverse(nums.begin() + firstIndex + 1, nums.end());
  }
};

三、交换一次的先前排列（中）

题目

给你一个正整数数组 arr（可能存在重复的元素），请你返回可在一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。
如果无法这么操作，就请返回原数组。

示例 1：
输入：$arr = [3,2,1]$
输出：$[3,1,2]$
解释：交换 2 和 1

示例 2：
输入：$arr = [1,1,5]$
输出：$[1,1,5]$
解释：已经是最小排列

示例 3：
输入：$arr = [1,9,4,6,7]$
输出：$[1,7,4,6,9]$
解释：交换 9 和 7

提示：
$1 <= arr.length <= 10^4$
$1 <= arr[i] <= 10^4$

题解

这题跟我『上一个排列』差不多，主要是它找的排列是两个元素调换位置的，不像『上一个排列』那样，元素可以全部重排。

那首先照搬『上一个排列』解法，最后交换 firstIndex 和 secondIndex ，不用 reverse 逆序排列。

class Solution {
 public:
  vector<int> prevPermOpt1(vector<int>& nums) {
    if (nums.size() == 0) {
      return nums;
    }
    int firstIndex = -1;
    for (int i = nums.size() - 2; i >= 0; i--) {
      if (nums[i] > nums[i + 1]) {
        firstIndex = i;
        break;
      }
    }
    if (firstIndex == -1) {
      return nums;
    }
    int secondIndex = -1;
    for (int i = nums.size() - 1; i > 0; i--) {
      if (nums[i] < nums[firstIndex]) {
        if (nums[i] == nums[i - 1]) {
          // 防止有相邻重复元素出现,比如[3,1,1,4]
          continue;
        }
        secondIndex = i;
        break;
      }
    }
    int temp = nums[firstIndex];
    nums[firstIndex] = nums[secondIndex];
    nums[secondIndex] = temp;
    return nums;
  }
};