成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode] Permutation Sequence

Jacendfeng / 3138人閱讀

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

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65616.html

相關(guān)文章

  • [LintCode] Next Permutation II [Next Permutation]

    摘要：從末位向前遍歷，假設(shè)循環(huán)開始全是倒序排列，如當(dāng)?shù)谝淮纬霈F(xiàn)正序的時(shí)候，如的和此時(shí)從數(shù)列末尾向前循環(huán)到，找到第一個(gè)比大的交換這兩個(gè)數(shù)，變成倒置第位到末位的數(shù)為正序排列這里的是完全倒置的排列，如，即上面循環(huán)的情況完全沒有出現(xiàn)， Problem Implement next permutation, which rearranges numbers into the lexicographic...

    mikasa 評(píng)論0 收藏0

  • [LintCode] Permutation Index I & Permutation I

    摘要：我覺得雖然在里分類是，但其實(shí)是一道難題。思路如下搞一個(gè)哈希表，存儲(chǔ)數(shù)組中每一位的后面小于它的數(shù)的個(gè)數(shù)。與上一題的不同之處時(shí)會(huì)有重復(fù)的數(shù)。當(dāng)然，每個(gè)重復(fù)數(shù)的都要階乘，例如有個(gè)，個(gè)，就是。是所有排列的次數(shù)和，返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

    lucas 評(píng)論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 評(píng)論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 評(píng)論0 收藏0

  • [Leetcode] Permutation Sequence 全排列序列

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

    testHs 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<