leetcode：31. 下一个排列

题目

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

  • 例如，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]
  2. 输出：[1,3,2]
  1. 输入：nums = [3,2,1]
  2. 输出：[1,2,3]
  1. 输入：nums = [1,1,5]
  2. 输出：[1,5,1]

解答 & 代码

  • 要使得排列的字典序变大，那么要将一个左边的“较小数”和右边的“较大数”交换
  • 要得到下一个排列，那么不能变大太多，因此要找到一个最靠右的“较小数”，再找到尽可能小的“较大数”和它交换，交换完后，较大数右边的序列应该逆序（原本是降序的，改为升序）

[中等] 31. 下一个排列 - 图1

  1. class Solution {
  2. private:
  3.     // 数组 nums[left, right] 部分降序（非递增），找到最小的（即最左边）比target大的元素下标
  4.     int findMinGreaterIdx(vector<int>& nums, int left, int right, int target)
  5.     {
  6.         int idx = left;
  7.         while(left <= right)
  8.         {
  9.             int mid = left + (right - left) / 2;
  10.             if(nums[mid] > target)
  11.             {
  12.                 idx = mid;
  13.                 left = mid + 1;
  14.             }
  15.             else
  16.                 right = mid - 1;
  17.         }
  18.         return idx;
  19.     }
  20. public:
  21.     void nextPermutation(vector<int>& nums) {
  22.         int idx = nums.size() - 1;
  23.         // 1. 从右往左遍历数组，找到第一个 nums[idx] > nums[idx-1] 的位置 idx
  24.         //    即，找到从右往左第一个降低的元素下标 idx - 1
  25.         while(idx - 1 >= 0 && nums[idx] <= nums[idx - 1])
  26.             --idx;
  28.         // 如果 idx == 0，说明数组本身是降序的，就是最大排列，因此直接逆序变成最小排列，返回
  29.         if(idx == 0)
  30.             reverse(nums.begin(), nums.end());
  31.         // 否则，
  32.         else
  33.         { 
  34.             // 2. 找到 idx -1 后面部分（降序）比 nums[idx-1] 大的最小元素下标 minGreaterIdx
  35.             // 这里用的二分查找，也可以直接从右往左遍历
  36.             int minGreaterIdx = findMinGreaterIdx(nums, idx, nums.size() - 1, nums[idx - 1]);
  37.             // 3. 交换 nums[idx - 1] 和 nums[minGreaterIdx]
  38.             swap(nums[idx - 1], nums[minGreaterIdx]);
  39.             // 4. 将 idx - 1 后面部分变为升序（原本是降序，因此下面的排序操作也可以改为逆序操作）
  40.             sort(nums.begin() + idx, nums.end());
  41.         }
  42.     }
  43. };

复杂度分析：

  • 时间复杂度 O(N)：
  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 73.97% 的用户
  4. 内存消耗：11.6 MB, 在所有 C++ 提交中击败了 92.49% 的用户