一: 解题思路
Time:O(n),Space:O(1)
二: 完整代码示例 (C++ 版和 Java 版)
C++:
- class Solution {
- public:
- void nextPermutation(vector<int>& nums)
- {
- if (nums.size() == 0) return;
- int n = nums.size();
- int p = n - 2;
- while (p>= 0 && nums[p]>= nums[p + 1]) p--;
- if (p>= 0)
- {
- int i = n - 1;
- while (i> p && nums[i] <= nums[p]) i--;
- swap(nums[p],nums[i]);
- }
- for (int i = p + 1, j = n - 1; i <j; i++, j--)
- swap(nums[i],nums[j]);
- }
- };
Java:
- class Solution
- {
- private void swap(int[] nums,int i,int j)
- {
- int temp=nums[i];
- nums[i]=nums[j];
- nums[j]=temp;
- }
- public void nextPermutation(int[] nums)
- {
- if(nums==null || nums.length<2) return;
- int n=nums.length;
- int p=n-2;
- while (p>=0 && nums[p]>=nums[p+1]) p--;
- if(p>=0)
- {
- int i=n-1;
- while (i>p && nums[i]<=nums[p]) i--;
- swap(nums,i,p);
- }
- for(int i=p+1,j=n-1;i<j;i++,j--)
- {
- swap(nums,i,j);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3506853.html