[LintCode] Permutation Sequence

Jacendfeng 發布于2019-08-14 15:19 / 3118人閱讀

摘要：做法先把這個數放入一個數組里，同時計算出的階乘。假設這一組是第組，第一個數就是，同時刪去這個數，并讓除以取余作為新的。如此循環，這樣，下一組的成員數減少了，要找的位置也更為精確了。

Problem

Given n and k, return the k-th permutation sequence.

Example

For n = 3, all permutations are listed as follows:

"123"
"132"
"213"
"231"
"312"
"321"
If k = 4, the fourth permutation is "231".

Note

做法：先把這n個數放入一個數組nums里，同時計算出n的階乘fact。
然后我們去建立第k個數，也就是java計數規則里的第k-1個數，所以先k--。
怎么建立第k個數呢？這個數有n位數字，所以用0到n-1的for循環來做。
這里應用了一個規律，確定第一個數，有n種選擇，每種選擇有(n-1)!種情況。選定第一個數之后，選擇第二個數，有n-1種選擇，每種選擇有(n-2)!種情況。選定了前兩個數，選擇第三個數，有n-2種選擇，每種選擇有(n-3)!種情況。這樣，總共有n!個數，每層循環的樣本減少為fact/(n-i)。
所以我們找第k個數，可以先確定它的第一位，從前往后類推。
怎么確定第1位？如上所說，有n種選擇，也就是將所有情況分為n組，每種包含(n-1)!個成員。那么，第k個數除以(n-1)!就可以得到這個數在第幾組。假設這一組是第m組，第一個數就是nums.get(m)，同時刪去這個數，并讓k除以(n-1)!取余作為新的k。
之后，把這個數從nums里刪去，這樣剩余n-1個數的相對位置不變，然后在這一組里找新的第k個數。如此循環，這樣，下一組的成員數減少了，要找的位置k也更為精確了。

Some Examples

//1234, n = 4, k = 15,

k = 14, fact = 24,
fact = 24/4 = 6, cur = k/fact = 14/6 = 2, k = k%fact = 2,
nums.get(cur) = 3,
fact = 6/3 = 2, cur = k/fact = 2/2 = 1, k = k%fact = 0,
nums.get(cur) = 2,
fact = 2/2 = 1, cur = k/fact = 0, k = k%fact = 0,
nums.get(0) = 1,
therefore, 3214.

//1234, n = 4, k = 7,

k = 6, fact = 24,
fact = 24/4 = 6, cur = k/fact = 1, k = k%fact = 0,
nums.get(cur) = 2,
fact = 6/3 = 2, cur = 0, nums.get(0) = 1,
cur = 0, nums.get(0) = 3,
cur = 0, nums.get(0) = 4,
therefore, 2134.

//1234, n = 4, k = 22,

k = 21, fact = 24,
fact = 24/4 = 6, cur = k/fact = 3, k = k%fact = 3, 
nums.get(3) = 4,
fact = 2, cur = 3/2 = 1, k = 3%2 = 1, 
nums.get(1) = 2,
fact = 1, cur = 1/1 = 1, k = 1%1 = 0,
nums.get(0) = 3,
fact = 1, cur = 0/1 = 0, k = 0%1 = 0,
nums.get(0) = 1,
therefore, 4231.

Solution

class Solution {
    public String getPermutation(int n, int k) {
        ArrayList nums = new ArrayList();
        int fact = 1;
        for (int i = 1; i <= n; i++) {
            nums.add(i);
            fact *= i;
        }
        k--;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            fact /= (n-i);
            int cur = k / fact;
            k %= fact;
            sb.append(nums.get(cur));
            nums.remove(cur);
        }
        return sb.toString();
    }
}

云服務器 GPU云服務器 Sequence Permutation LintCode LintCode134_LRU

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65616.html

[LintCode] Next Permutation II [Next Permutation]

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

mikasa 2019-08-14 15:15 評論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
[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
[Leetcode] Permutation Sequence 全排列序列

摘要：找規律復雜度時間空間思路由于我們只要得到第個全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據全排列順序的性質，我們可以總結出一個規律假設全排列有個數組成，則第個全排列的第一位是。然后將得到，這個就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 評論0 收藏0