兩分鐘看完一道數學思想的算法題

點選藍色“五分鐘學算法”關注我喲

加個“星标”，天天中午 12:15，一起學算法

作者 | P.yh

來源 | 五分鐘學算法

題目描述

給你數字 0 ，1 ，2 ，那麼所有排列從小到大就會是 012，021，102，120，201，210，那麼如果給你 0，1，2，3，4，5，6，7，8，9 讓你去排，從小到大排在第一百萬的數是多少？

題目位址：https://projecteuler.net/problem=24

題目解析

寫普通算法程式題寫多了，見到排列首當其沖想到用深度優先搜尋，最後發現如果把所有的排列可能都給列出來，然後排序，這樣搞下來程式運作的時間複雜度是 O(n!)，比指數的時間複雜度還要高！

如果從數學思路上去思考的話，那問題就簡單了！

通過一個數一個數的去選。

首先第一個位置（最高位）有十種可能性，我們可以利用 10! / 10 來計算出每一個數字打頭有多少種排列，然後用一百萬 / (10! / 10) 來決定我們要選排在第幾的數，選中一個數後，剩下的數就隻有 9 個，将 10 換成 9，重複上面的操作，當然，一百萬這個值也得根據我們找的數來做更新，比如你第一個數選擇了 2，那麼 0 和 1 打頭的 2 * 10! / 10 種組合都可以減掉，剩下的我們需要繼續在後面的 9 個數的排列中找。

代碼實作

//@author:P.yh
public static void main(String[] args) {
    System.out.println(lexicographicPermu(10, 1000000L));
}

private static String lexicographicPermu(int numberOfDigit, long target) {
    int copyOfNumerOfDigit = numberOfDigit;
    long copyOfTarget = target;

    // list 裡面存放的是所有的可以選擇的情況，并從大到小排列
    // 這裡是 0，1，2，3，4，5，6，7，8，9
    List<Integer> candidate = new ArrayList<>();
    for (int i = 0; i < copyOfNumerOfDigit; ++i) {
        candidate.add(i);
    }

    String result = "";

    // 隻要沒有選完，就繼續選擇
    while (copyOfNumerOfDigit != 0) {
        long totalPermutation = 1;
        int n = copyOfNumerOfDigit;

        // 計算 n!
        // 例如，選擇第一個數，那 totalPermutation 就是 10!
        while (n != 1) {
            totalPermutation *= n;
            n--;
        }

        // 計算選擇目前情況下的第幾個數
        // 這裡 copyOfTarget - 1 是為了防止整除的情況
        // 舉 0，1，2 這個例子，當我們要選擇排在第 2 的那個數，也就是 021
        // 選第一個數的時候， totalPermutation = 3 * 2 * 1 = 6, copyOfNumberOfDigit = 3
        // 2 / (6 / 3) = 1，顯然不符合要求，(2 - 1) / (6 / 3) = 0 才是選中了 0
        int selection = (int)((copyOfTarget - 1) / (totalPermutation / copyOfNumerOfDigit));
        result += candidate.remove(selection);

        // 更新下一次要選擇第幾個數
        copyOfTarget -= (totalPermutation / copyOfNumerOfDigit) * selection;

        // 選了一個數，可選項相應減少一
        copyOfNumerOfDigit--;
        copyOfTarget = copyOfTarget <= 0 ? 0 : copyOfTarget;
    }

    return result;
}

複制