LeeCode : 31. Next Permutation 下一全排列字典序排列

缺乏、安全感 2021-09-19 07:18 314阅读 0赞

**试题**  
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2  
3,2,1 → 1,2,3  
1,1,5 → 1,5,1

**代码**  
[主要有三步：找到小于，找到大于，尾部翻转][Link 1]

class Solution {
        public void nextPermutation(int[] nums) {
            if(nums==null || nums.length<=1) return;
            int len = nums.length;
            
            int cur = len-1;
            while(cur-1>=0 && nums[cur-1]>=nums[cur]) cur--;
            if(cur==0){
                reverse(nums, 0, len-1);
                return;
            }
            
            cur--;
            int lo = cur;
            while(cur+1<len && nums[cur+1]>nums[lo]) cur++;
            swap(nums, lo, cur);
            reverse(nums, lo+1, len-1);
            return;
        }
        
        public void reverse(int[] nums, int left, int right){
            while(left<right){
                swap(nums, left, right);
                left++;
                right--;
            }
        }
        
        public void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

[Link 1]: https://blog.csdn.net/qq_16234613/article/details/77169300

发表评论取消回复

表情：

评论列表（有 0 条评论，314人围观）

还没有评论，来说两句吧...

相关阅读

相关 Next Permutation（C++下一个排列）

(1) 模拟法 class Solution { public: void nextPermutation(vector<int>& n

迈不过友情╰/ 2022年10月09日 12:17/ 0 赞/ 115 阅读

相关【日常学习】【全排列】next_permutation函数版全排列

今天蒙花将军提醒，在ruka(紫书)上发现了全排列的一种新方法，应用了next\_permutation函数，这是一个专门求下一个全排列的函数，在算法库里 inclu

超、凢脫俗/ 2022年08月09日 06:27/ 0 赞/ 170 阅读

相关 1384 全排列 next_permutation()函数

思路：（1）将输入的字符数组转化为整数数组；（2）使用qsort()函数将整数数组进行从小到大的快排；（3）使用next\_permutation()函数依次

女爷i/ 2022年06月07日 02:59/ 0 赞/ 154 阅读

相关 next_permutation(全排列算法)

STL提供了两个用来计算排列组合关系的算法，分别是next\_permutation和prev\_permutation。首先我们必须了解什么是“下一个”排列组合，什么是“前一

淡淡的烟草味﹌/ 2022年05月19日 10:44/ 0 赞/ 203 阅读

相关 LeetCode 31.Next Permutation (下一个排列)

题目描述：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

约定不等于承诺〃/ 2022年05月11日 04:04/ 0 赞/ 178 阅读

相关 31. Next Permutation【下一个排列】

Implement next permutation, which rearranges numbers into the lexicographically next gre

﹏ヽ暗。殇╰゛Y/ 2022年04月23日 06:24/ 0 赞/ 153 阅读

相关 C++ STL 字典序排列之强大的next_permutation

之前见到过这个 C++ 里面强大的库函数可惜之后又忘记了所以嗯现在整理一下首先头文件 \include<algorithm> next\_

刺骨的言语ヽ痛彻心扉/ 2022年04月18日 05:11/ 0 赞/ 442 阅读

相关 Next Permutation Algorithm，取得全排列中当前排列的下一个排列

Next Permutation算法给定一个整数数组，数组中的每一个元素均为0~9之间的整数，如下算法能够高效取得在该数组按数字从小到大排列的全排列中的下一个排列。给定

清疚/ 2022年03月01日 04:12/ 0 赞/ 198 阅读

相关全排列 -- next_permutation()

头文件：\include <algorithm> 实现： 1 int main() 2 { 3 int a[15]; 4 fo

ゞ浴缸里的玫瑰/ 2021年12月09日 14:53/ 0 赞/ 246 阅读

相关 LeeCode : 31. Next Permutation 下一全排列字典序排列

试题 Implement next permutation, which rearranges numbers into the lexicographically nex

缺乏、安全感/ 2021年09月19日 07:18/ 0 赞/ 315 阅读