下一个排列 lintcode

古城微笑少年丶 2022-07-15 00:46 173阅读 0赞

####  下一个排列 ####

*  [ 描述][Link 1]
 *  [ 笔记][Link 2]
 *  [ 数据][Link 3]
 *  [ 评测][Link 4]

给定一个若干整数的排列，给出按正数大小进行字典序从小到大排序后的下一个排列。

如果没有下一个排列，则输出字典序最小的序列。

您在真实的面试中是否遇到过这个题？

Yes

样例

左边是原始排列，右边是对应的下一个排列。

`1,2,3` → `1,3,2`

`3,2,1` → `1,2,3`

`1,1,5` → `1,5,1`

[挑战 ][Link 5]

不允许使用额外的空间。

[标签 ][Link 6]

[排列][Link 7] [数组][Link 8]

public class Solution {
        /**
         * @param nums: an array of integers
         * @return: return nothing (void), do not return anything, modify nums in-place instead
         */
        public void nextPermutation(int[] nums) {
            // write your code here
            int n = nums.length;
            for(int i=n-1;i>=0;i--)
            {
                for(int j=n-1;j>i;j--)
                {
                    if(nums[i]<nums[j])
                    {   
                        int tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                        Arrays.sort(nums,i+1,nums.length);
                        return;
                    }
                }
            }
            Arrays.sort(nums);
        }
    }

[Link 1]: http://www.lintcode.com/zh-cn/problem/next-permutation-ii/#description
[Link 2]: http://www.lintcode.com/zh-cn/problem/next-permutation-ii/#note
[Link 3]: http://www.lintcode.com/zh-cn/problem/next-permutation-ii/#testcase
[Link 4]: http://www.lintcode.com/zh-cn/problem/next-permutation-ii/#judge
[Link 5]: http://www.lintcode.com/zh-cn/problem/next-permutation-ii/#challenge
[Link 6]: http://www.lintcode.com/zh-cn/problem/next-permutation-ii/#tags
[Link 7]: http://www.lintcode.com/tag/permutation/
[Link 8]: http://www.lintcode.com/tag/array/