[LintCode] Permutation Index I & Permutation I

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

摘要：我覺得雖然在里分類是，但其實是一道難題。思路如下搞一個哈希表，存儲數(shù)組中每一位的后面小于它的數(shù)的個數(shù)。與上一題的不同之處時會有重復的數(shù)。當然，每個重復數(shù)的都要階乘，例如有個，個，就是。是所有排列的次數(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

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

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

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ù)。那么，只要在發(fā)現(xiàn)是重復數(shù)的那一位用rank * fact的結果除以重復的次數(shù)dup再加入index就可以了。當然，每個重復數(shù)的dup都要階乘，例如有3個2，4個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;
    }
}

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

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66193.html

[LintCode] Next Permutation II [Next Permutation]

摘要：從末位向前遍歷，假設循環(huán)開始全是倒序排列，如當?shù)谝淮纬霈F(xiàn)正序的時候，如的和此時從數(shù)列末尾向前循環(huán)到，找到第一個比大的交換這兩個數(shù)，變成倒置第位到末位的數(shù)為正序排列這里的是完全倒置的排列，如，即上面循環(huán)的情況完全沒有出現(xiàn)， 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

摘要：做法先把這個數(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 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解三階幻方謎題

摘要：謎題三階幻方。試將這個不同整數(shù)填入一個的表格，使得每行每列以及每條對角線上的數(shù)字之和相同。列出所有的整數(shù)填充方案，然后進行過濾。 /* * 謎題--三階幻方。 * 試將1~9這9個不同整數(shù)填入一個3×3的表格，使得每行、每列以及每條對角線上的數(shù)字之和相同。 * 策略 * 窮舉搜索。列出所有的整數(shù)填充方案，然后進行過濾。 * 亮點為遞歸函數(shù)getPermut...

Render 2019-08-21 10:24 評論0 收藏0