美文网首页
下一个排列

下一个排列

作者: 小白学编程 | 来源:发表于2018-10-29 09:07 被阅读0次

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

必须原地修改,只允许使用额外常数空间。

以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

思路

在当前序列中,从尾端往前寻找两个相邻元素,前一个记为first,后一个记为second,并且满足first 小于 second。然后再从尾端寻找另一个元素number,如果满足first 小于number,即将第first个元素与number元素对调,并将second元素之后(包括second)的所有元素颠倒排序,即求出下一个序列

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length <= 1) {
            return ;
        }
        int f = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                f = i;
                break;
            }
        }
        int s = 0;
        if (f - 1 >= 0) {
            for (int i = nums.length - 1; i > 0; i--) {
                if (nums[i] > nums[f - 1]) {
                    s = i;
                    break;
                }
            }
            swap(nums, s, f - 1);
        }
            
        reverse(nums, f, nums.length - 1);
        
       
        
    }
    
    public void reverse(int[] nums, int l, int r) {

        while (l < r) {
            swap(nums, l, r);
            l++;
            r--;
        }
        
        
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

相关文章

  • 全排列系列总结

    一. 找到下一个全排列 这是给定一个排列,找它的下一个全排列 给出一个数字排列中按字典序排列的下一个更大的排列。如...

  • LeetCode 31. 下一个排列 | Python

    31. 下一个排列 题目 实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如...

  • 31. 下一个排列

    31. 下一个排列 实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存...

  • 31-下一个排列

    下一个排列 题目 实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在...

  • LeetCode每日一题: 31. 下一个排列

    31. 下一个排列 实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在...

  • 31. 下一个排列

    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列,则...

  • 下一个排列

    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列,...

  • 下一个排列

    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列,则...

  • 【LeetCode】排列问题

    31.下一个排列 实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下...

  • leetcode 031. 下一个排列

    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列,...

网友评论

      本文标题:下一个排列

      本文链接:https://www.haomeiwen.com/subject/isiptqtx.html