[LintCode] Permutation Index I & Permutation I

lucas 發(fā)布于2019-08-14 16:23 / 1284人閱讀

摘要：我覺(jué)得雖然在里分類(lè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 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

我覺(jué)得雖然在LC里分類(lèi)是Easy，但其實(shí)是一道難題。思路如下：
搞一個(gè)哈希表，存儲(chǔ)數(shù)組A中每一位A[i]的后面小于它的數(shù)的個(gè)數(shù)count。
為什么這樣做呢，因?yàn)榘凑?strong>lexicographical order，小的數(shù)應(yīng)該排在前面。那么A[i]后面小于A[i]的數(shù)有count個(gè)，而i前面又應(yīng)該有n-i-1位，有(n-1-i)的階乘種排列的可能，所以應(yīng)該排在A[i]之前的可能排列就有count * (n-1-i)!個(gè)：所以遍歷A[]中每一個(gè)數(shù)，計(jì)算在其之前的自然排列的數(shù)目，這些數(shù)目相加之和存入res，那么res的下一個(gè)數(shù)字就是現(xiàn)在數(shù)組A[]的排列。

對(duì)題目有了思索和理解之后，可以找找簡(jiǎn)化一點(diǎn)的辦法。有沒(méi)有可能不使用HashMap，也能夠記錄階乘呢？只要從最后一位fact = 1開(kāi)始, 向高位階乘，直到最高位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

//這種思路是從高位向低位計(jì)算當(dāng)前位剩余排列總數(shù)，階乘逐位減小，理解起來(lái)就沒(méi)有那么直觀了。

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

與上一題的不同之處時(shí)會(huì)有重復(fù)的數(shù)。那么，只要在發(fā)現(xiàn)是重復(fù)數(shù)的那一位用rank * fact的結(jié)果除以重復(fù)的次數(shù)dup再加入index就可以了。當(dāng)然，每個(gè)重復(fù)數(shù)的dup都要階乘，例如有3個(gè)2，4個(gè)8，dup就是3! * 4! = 144。index是所有previous排列的次數(shù)和，返回下一次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;
    }
}