[LintCode] Next Permutation II [Next Permutation]

mikasa 發布于2019-08-14 15:15 / 2827人閱讀

摘要：從末位向前遍歷，假設循環開始全是倒序排列，如當第一次出現正序的時候，如的和此時從數列末尾向前循環到，找到第一個比大的交換這兩個數，變成倒置第位到末位的數為正序排列這里的是完全倒置的排列，如，即上面循環的情況完全沒有出現，

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--);
    }
}

云服務器 GPU云服務器 Permutation -next Next next.js

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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