[LintCode] Next Permutation II [Next Permutation]

mikasa 发布于2019-08-14 15:15 / 2698人阅读

摘要：从末位向前遍历，假设循环开始全是倒序排列，如当第一次出现正序的时候，如的和此时从数列末尾向前循环到，找到第一个比大的交换这两个数，变成倒置第位到末位的数为正序排列这里的是完全倒置的排列，如，即上面循环的情况完全没有出现，

Problem

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).

Example

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

Challenge

The replacement must be in-place, do not allocate extra memory.

Solution

public class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        if (nums == null || len == 0) return;
        //从末位向前遍历，（假设循环开始全是倒序排列，如65321）
        for (int i = len - 2; i >= 0; i--) {
            //当第一次出现正序的时候，如465321的4和6
            if (nums[i] < nums[i+1]) {
                //此时从数列末尾向前循环到i，
                //找到第一个比nums[i]大的nums[j]
                int j;
                for (j = len - 1; j >= i; j--) {
                    if (nums[j] > nums[i]) break;
                }
                //交换这两个数，变成564321
                swap(nums, i, j);
                //倒置第i+1位到末位的数为正序排列512346
                reverse(nums, i+1, len-1);
                return;
            }
        }
        //这里return的是完全倒置的排列，如654321，
        //即上面for循环的if情况完全没有出现，for循环没有做过任何操作
        reverse(nums, 0, len-1);
        return; 
    }
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    public void reverse(int[] A, int start, int end) {
        while (left < right) swap(A, start++, end--);
    }
}

简化一下，分别用while循环找i和j

public class Solution {
    public void nextPermutation(int[] A) {
        int n = A.length, i = n-2;
        while (i >= 0 && A[i] >= A[i+1]) i--;
        if (i >= 0) {
            int j = n-1;
            while (A[j] <= A[i]) j--;
            swap(A, i, j);
        }
        reverse(A, i+1, n-1);
        return;
    }
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    public void reverse(int[] A, int i, int j) {
        while (i < j) swap(A, i++, j--);
    }
}

混合云专线服务 Permutation -next Next next.js

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65494.html

[Leetcode]PermutationsI II Next Permutation Permut

摘要：解题思路这道题是要将排列按字典序排列，然后求出下一个排列，一种办法是我们先求出所有的排序情况，但是题目规定不能占有额外空间。每次求出一个数字后，要及时的把它从中删除掉。采用来构造结果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...

ChristmasBoy 2019-08-16 10:26 评论0 收藏0
[LintCode] Permutation Index I & Permutation I

摘要：我觉得虽然在里分类是，但其实是一道难题。思路如下搞一个哈希表，存储数组中每一位的后面小于它的数的个数。与上一题的不同之处时会有重复的数。当然，每个重复数的都要阶乘，例如有个，个，就是。是所有排列的次数和，返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

lucas 2019-08-14 16:23 评论0 收藏0
[Leetcode] Next Permutation 下一个排列

摘要：因为增加高位会带来更大的增益。所以对于一个长为的序列，我们增加第位的前提是，前位已经达到了最大排列方法。因为是找下一个数，所以我们要找一个比小却尽可能大的数，所以找到。把换到的位置后，后三位仍然是个降序的排列。 Next Permutation Implement next permutation, which rearranges numbers into the lexicogr...

young.li 2019-08-14 12:34 评论0 收藏0
[LintCode] Previous Permutation

Problem Given a list of integers, which denote a permutation. Find the previous permutation in ascending order. Notice The list may contains duplicate integers. Example For [1,3,2,3], the previous per...

Pines_Cheng 2019-08-14 15:44 评论0 收藏0
[LintCode] Permutation in String

Problem Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first strings permutations is the substring of the second string. ...

wenshi11019 2019-08-15 18:16 评论0 收藏0