[LintCode] Permutation Sequence

Jacendfeng 发布于2019-08-14 15:19 / 2880人阅读

摘要：做法先把这个数放入一个数组里，同时计算出的阶乘。假设这一组是第组，第一个数就是，同时删去这个数，并让除以取余作为新的。如此循环，这样，下一组的成员数减少了，要找的位置也更为精确了。

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

超融合服务器私有云 Sequence Permutation LintCode LintCode134_LRU

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

转载请注明本文地址：https://www.ucloud.cn/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