Next Permutation

Question

Problem Statement

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Example

For [1,3,2,3], the next permutation is [1,3,3,2]

For [4,3,2,1], the next permutation is [1,2,3,4]

Note

The list may contains duplicate integers.

題解

找下一個升序排列，C++ STL 源碼剖析一書中有提及，Permutations 一小節中也有詳細介紹，下面簡要介紹一下字典序算法：

  1. 從後往前尋找索引滿足 a[k] < a[k + 1], 如果此條件不滿足，則說明已遍歷到最後一個。
  2. 從後往前遍歷，找到第一個比a[k]大的數a[l], 即a[k] < a[l].
  3. 交換a[k]與a[l].
  4. 反轉k + 1 ~ n之間的元素。

由於這道題中規定對於[4,3,2,1], 輸出爲[1,2,3,4], 故在第一步稍加處理即可。

Python

  1. class Solution:
  2.     # @param num :  a list of integer
  3.     # @return : a list of integer
  4.     def nextPermutation(self, num):
  5.         if num is None or len(num) <= 1:
  6.             return num
  7.         # step1: find nums[i] < nums[i + 1], Loop backwards
  8.         i = 0
  9.         for i in xrange(len(num) - 2, -1, -1):
  10.             if num[i] < num[i + 1]:
  11.                 break
  12.             elif i == 0:
  13.                 # reverse nums if reach maximum
  14.                 num = num[::-1]
  15.                 return num
  16.         # step2: find nums[i] < nums[j], Loop backwards
  17.         j = 0
  18.         for j in xrange(len(num) - 1, i, -1):
  19.             if num[i] < num[j]:
  20.                 break
  21.         # step3: swap betwenn nums[i] and nums[j]
  22.         num[i], num[j] = num[j], num[i]
  23.         # step4: reverse between [i + 1, n - 1]
  24.         num[i + 1:len(num)] = num[len(num) - 1:i:-1]
  26.         return num

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param nums: An array of integers
  5.      * @return: An array of integers that's next permuation
  6.      */
  7.     vector<int> nextPermutation(vector<int> &nums) {
  8.         if (nums.empty() || nums.size() <= 1) {
  9.             return nums;
  10.         }
  11.         // step1: find nums[i] < nums[i + 1]
  12.         int i = 0;
  13.         for (i = nums.size() - 2; i >= 0; --i) {
  14.             if (nums[i] < nums[i + 1]) {
  15.                 break;
  16.             } else if (0 == i) {
  17.                 // reverse nums if reach maximum
  18.                 reverse(nums, 0, nums.size() - 1);
  19.                 return nums;
  20.             }
  21.         }
  22.         // step2: find nums[i] < nums[j]
  23.         int j = 0;
  24.         for (j = nums.size() - 1; j > i; --j) {
  25.             if (nums[i] < nums[j]) break;
  26.         }
  27.         // step3: swap betwenn nums[i] and nums[j]
  28.         int temp = nums[i];
  29.         nums[i] = nums[j];
  30.         nums[j] = temp;
  31.         // step4: reverse between [i + 1, n - 1]
  32.         reverse(nums, i + 1, nums.size() - 1);
  34.         return nums;
  36.     }
  38. private:
  39.     void reverse(vector<int>& nums, int start, int end) {
  40.         for (int i = start, j = end; i < j; ++i, --j) {
  41.             int temp = nums[i];
  42.             nums[i] = nums[j];
  43.             nums[j] = temp;
  44.         }
  45.     }
  46. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: an array of integers
  4.      * @return: return nothing (void), do not return anything, modify nums in-place instead
  5.      */
  6.     public void nextPermutation(int[] nums) {
  7.         if (nums == null || nums.length == 0) return;
  9.         // step1: search the first nums[k] < nums[k+1] backward
  10.         int k = -1;
  11.         for (int i = nums.length - 2; i >= 0; i--) {
  12.             if (nums[i] < nums[i + 1]) {
  13.                 k = i;
  14.                 break;
  15.             }
  16.         }
  17.         // if current rank is the largest, reverse it to smallest, return
  18.         if (k == -1) {
  19.             reverse(nums, 0, nums.length - 1);
  20.             return;
  21.         }
  23.         // step2: search the first nums[k] < nums[l] backward
  24.         int l = nums.length - 1;
  25.         while (l > k && nums[l] <= nums[k]) l--;
  27.         // step3: swap nums[k] with nums[l]
  28.         int temp = nums[k];
  29.         nums[k] = nums[l];
  30.         nums[l] = temp;
  32.         // step4: reverse between k+1 and nums.length-1;
  33.         reverse(nums, k + 1, nums.length - 1);
  34.     }
  36.     private void reverse(int[] nums, int lb, int ub) {
  37.         for (int i = lb, j = ub; i < j; i++, j--) {
  38.             int temp = nums[i];
  39.             nums[i] = nums[j];
  40.             nums[j] = temp;
  41.         }
  42.     }
  43. }

源碼分析

和 Permutation 一小節類似，這裏只需要注意在step 1中i == -1時需要反轉之以獲得最小的序列。對於有重復元素，只要在 step1和 step2中判斷元素大小時不取等號即可。Lintcode 上給的註釋要求（其實是 Leetcode 上的要求）和實際給出的輸出不一樣。

複雜度分析

最壞情況下，遍歷兩次原陣列，反轉一次陣列，時間複雜度爲 O(n), 使用了 temp 臨時變量，空間複雜度可認爲是 O(1).