亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[LintCode] Permutation Sequence

Jacendfeng / 3167人閱讀

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

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/65616.html

相關(guān)文章

  • [LintCode] Next Permutation II [Next Permutation]

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

    mikasa 評論0 收藏0

  • [LintCode] Permutation Index I & Permutation I

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

    lucas 評論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 評論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 評論0 收藏0

  • [Leetcode] Permutation Sequence 全排列序列

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

    testHs 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<