[LintCode] Permutation Index I & Permutation I

lucas 发布于2019-08-14 16:23 / 1186人阅读

摘要：我觉得虽然在里分类是，但其实是一道难题。思路如下搞一个哈希表，存储数组中每一位的后面小于它的数的个数。与上一题的不同之处时会有重复的数。当然，每个重复数的都要阶乘，例如有个，个，就是。是所有排列的次数和，返回下一次。

Permutation Index Problem

Given a permutation which contains no repeated number, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.

Example

Given [1,2,4], return 1.

Note

我觉得虽然在LC里分类是Easy，但其实是一道难题。思路如下：
搞一个哈希表，存储数组A中每一位A[i]的后面小于它的数的个数count。
为什么这样做呢，因为按照lexicographical order，小的数应该排在前面。那么A[i]后面小于A[i]的数有count个，而i前面又应该有n-i-1位，有(n-1-i)的阶乘种排列的可能，所以应该排在A[i]之前的可能排列就有count * (n-1-i)!个：所以遍历A[]中每一个数，计算在其之前的自然排列的数目，这些数目相加之和存入res，那么res的下一个数字就是现在数组A[]的排列。

对题目有了思索和理解之后，可以找找简化一点的办法。有没有可能不使用HashMap，也能够记录阶乘呢？只要从最后一位fact = 1开始, 向高位阶乘，直到最高位fact = A.length!。

Solution

public class Solution {
    public long permutationIndex(int[] A) {
        int n = A.length;
        long res = 0;
        HashMap map = new HashMap();
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = i+1; j < n; j++) {
                if (A[i] > A[j]) count++;
            }
            map.put(A[i], count);
        }
        for (int i = 0; i < n; i++) {
            long fact = 1;
            for (int j = n-1-i; j > 0; j--) {
                fact *= j;
            }
            res += map.get(A[i]) * fact;
        }
        return ++res;
    }
}

public class Solution {
    public long permutationIndex(int[] A) {
        if (A == null || A.length == 0) return 0;
        long fact = 1, index = 0;
        for (int i = A.length-1; i >= 0; i--) {
            int rank = 0;
            for (int j = i+1; j < A.length; j++) {
                if (A[j] < A[i]) rank++;
            }
            index += rank * fact;
            fact *= (A.length-i);
        }
        return index+1;
    }
}

vs. i increases in for loop

//这种思路是从高位向低位计算当前位剩余排列总数，阶乘逐位减小，理解起来就没有那么直观了。

public class Solution {
    public long permutationIndex(int[] A) {
        if (A == null || A.length == 0) return 0;
        long index = 0, fact = 1;
        for (int i = 1; i <= A.length; i++) fact *= i;
        for (int i = 0; i < A.length; i++) {
            int rank = 0;
            for (int j = i+1; j < A.length; j++) {
                if (A[j] < A[i]) rank++;
            }
            fact /= (A.length-i);
            index += rank * fact;
        }
        return index+1;
    }
}

Permutation Index II Problem

Given a permutation which may contain repeated numbers, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.

Example

Given the permutation [1, 4, 2, 2], return 3.

Note

与上一题的不同之处时会有重复的数。那么，只要在发现是重复数的那一位用rank * fact的结果除以重复的次数dup再加入index就可以了。当然，每个重复数的dup都要阶乘，例如有3个2，4个8，dup就是3! * 4! = 144。index是所有previous排列的次数和，返回下一次index+1。

Solution

public class Solution {
    public long permutationIndexII(int[] A) {
        long index = 0, fact = 1, dup = 1;
        HashMap map = new HashMap();
        for (int i = A.length-1; i >= 0; i--) {
            if (!map.containsKey(A[i])) map.put(A[i], 1);
            else {
                map.put(A[i], map.get(A[i])+1);
                dup *= map.get(A[i]);
            }
            int rank = 0;
            for (int j = i+1; j < A.length; j++) {
                if (A[j] < A[i]) rank++;
            }
            index += rank * fact / dup;
            fact *= (A.length - i);
        }
        return index+1;
    }
}

云服务器 GPU云服务器 Permutation index. index i+1&lti java

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

转载请注明本文地址：https://www.ucloud.cn/yun/66193.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 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
[LintCode] Permutation Sequence

摘要：做法先把这个数放入一个数组里，同时计算出的阶乘。假设这一组是第组，第一个数就是，同时删去这个数，并让除以取余作为新的。如此循环，这样，下一组的成员数减少了，要找的位置也更为精确了。 Problem Given n and k, return the k-th permutation sequence. Example For n = 3, all permutations are li...

Jacendfeng 2019-08-14 15:19 评论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
javascript解三阶幻方谜题

摘要：谜题三阶幻方。试将这个不同整数填入一个的表格，使得每行每列以及每条对角线上的数字之和相同。列出所有的整数填充方案，然后进行过滤。 /* * 谜题--三阶幻方。 * 试将1~9这9个不同整数填入一个3×3的表格，使得每行、每列以及每条对角线上的数字之和相同。 * 策略 * 穷举搜索。列出所有的整数填充方案，然后进行过滤。 * 亮点为递归函数getPermut...

Render 2019-08-21 10:24 评论0 收藏0