题目描述

原题链接

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

  • 例如，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

个人解法

Java

  1. class Solution {
  2.     public void nextPermutation(int[] nums) {
  3.         //34211--41123  43211
  4.         //24311--41123 42311 231 312 132 213
  5.         int len = nums.length, flag = 0, temp, x = 0;
  6.         if (len == 2) {
  7.             temp = nums[0];
  8.             nums[0] = nums[1];
  9.             nums[1] = temp;
  10.         } else {
  11.             for (int i = len - 1; i > 0; i--) {
  12.                 if (nums[i] > nums[i - 1]) {
  13.                     for (int j = len - 1; j > i; j--) {
  14.                         if (nums[j] > nums[i - 1]) {
  15.                             temp = nums[j];
  16.                             nums[j] = nums[i - 1];
  17.                             nums[i - 1] = temp;
  18.                             x = 1;
  19.                             break;
  20.                         }
  21.                     }
  22.                     if (x == 0) {
  23.                         temp = nums[i];
  24.                         nums[i] = nums[i - 1];
  25.                         nums[i - 1] = temp;
  26.                     }
  27.                     flag = i;
  28.                     break;
  29.                 }
  30.             }
  31.             //f len 1 2 3 4 5
  32.             for (int i = flag + 1; i < len; i++) {
  33.                 if (nums[flag] > nums[i]) {
  34.                     temp = nums[i - 1];
  35.                     nums[i - 1] = nums[flag];
  36.                     nums[flag] = temp;
  37.                     break;
  38.                 }
  39.             }
  40.             for (int i = flag; i < (len + flag) / 2; i++) {
  41.                 temp = nums[i];
  42.                 nums[i] = nums[flag + len - 1 - i];
  43.                 nums[flag + len - 1 - i] = temp;
  44.             }
  45.         }
  46.     }
  48. }

本质一样的解法，写的短一点，但是速度比较慢，因为调用了包装类自带的方法

  1. public void nextPermutation(int[] nums) {
  2.         int len = nums.length, flag = 0, temp, x = 0;
  3.         for (int i = len - 1; i > 0; i--) {
  4.             if (nums[i] > nums[i - 1]) {
  5.                 for (int j = len - 1; j > i; j--) {
  6.                     if (nums[j] > nums[i - 1]) {
  7.                         temp = nums[j];
  8.                         nums[j] = nums[i - 1];
  9.                         nums[i - 1] = temp;
  10.                         x = 1;
  11.                         break;
  12.                     }
  13.                 }
  14.                 if (x == 0) {
  15.                     temp = nums[i];
  16.                     nums[i] = nums[i - 1];
  17.                     nums[i - 1] = temp;
  18.                 }
  19.                 flag = i;
  20.                 break;
  21.             }
  22.         }
  23.         Arrays.sort(nums,flag,len);
  24.     }

JavaScript

不会

其他解法

JavaScript

看题解后自己的写法

  1. /*
  2.  * @lc app=leetcode.cn id=31 lang=javascript
  3.  *
  4.  * [31] 下一个排列
  5.  */
  7. // @lc code=start
  8. /**
  9.  * @param {number[]} nums
  10.  * @return {void} Do not return anything, modify nums in-place instead.
  11.  */
  12. var nextPermutation = function (nums) {
  13.   if (nums.length <= 1) {
  14.     return;
  15.   }
  16.   const length = nums.length;
  17.   let left = length - 2;
  18.   let right = length - 1;
  19.   while (left >= 0) {
  20.     if (nums[left] < nums[right]) {
  21.       break;
  22.     }
  23.     left--;
  24.     right--;
  25.   }
  26.   if (left > -1) {
  27.     let k = length - 1;
  28.     for (; k > left; k--) {
  29.       if (nums[k] > nums[left]) {
  30.         break;
  31.       }
  32.     }
  33.     let temp = nums[left];
  34.     nums[left] = nums[k];
  35.     nums[k] = temp;
  36.     nums.splice(right, length - right, ...nums.slice(right).reverse());
  37.   } else {
  38.     nums = nums.reverse();
  39.   }
  40. };
  41. // @lc code=end

他人解法

  1. function nextPermutation(nums) {
  2.     let i = nums.length - 2;                   // 向左遍历，i从倒数第二开始是为了nums[i+1]要存在
  3.     while (i >= 0 && nums[i] >= nums[i + 1]) { // 寻找第一个小于右邻居的数
  4.         i--;
  5.     }
  6.     if (i >= 0) {                             // 这个数在数组中存在，从它身后挑一个数，和它换
  7.         let j = nums.length - 1;                // 从最后一项，向左遍历
  8.         while (j >= 0 && nums[j] <= nums[i]) {  // 寻找第一个大于 nums[i] 的数
  9.             j--;
  10.         }
  11.         [nums[i], nums[j]] = [nums[j], nums[i]]; // 两数交换，实现变大
  12.     }
  13.     // 如果 i = -1，说明是递减排列，如 3 2 1，没有下一排列，直接翻转为最小排列：1 2 3
  14.     let l = i + 1;           
  15.     let r = nums.length - 1;
  16.     while (l < r) {                            // i 右边的数进行翻转，使得变大的幅度小一些
  17.         [nums[l], nums[r]] = [nums[r], nums[l]];
  18.         l++;
  19.         r--;
  20.     }
  21. }

Java