這是小川的第413次更新，第446篇原創(chuàng)

看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第264題（順位題號(hào)是1175）。返回1到n的排列數(shù)，以使質(zhì)數(shù)處于質(zhì)數(shù)索引（索引從1開(kāi)始）。（請(qǐng)記住，當(dāng)且僅當(dāng)整數(shù)大于1，并且不能將其寫(xiě)為兩個(gè)均小于它的正整數(shù)的乘積，它才是質(zhì)數(shù)。）由于答案可能很大，因此請(qǐng)以10^9 + 7為模返回答案。

例如：

輸入：n = 5
輸出：12
說(shuō)明：[1,2,5,4,3]是有效的排列，但是[5,2,3,4,1]并不是，因?yàn)樗財(cái)?shù)5在索引1處。

輸入：n = 100
輸出：682289015

注意：

• 1 <= n <= 100
  
  

解題

題目的意思是計(jì)算一個(gè)由1到n組成的數(shù)列中，質(zhì)數(shù)恰好位于質(zhì)數(shù)索引上的排列組合個(gè)數(shù)，本質(zhì)上是一個(gè)數(shù)學(xué)問(wèn)題。

結(jié)合n = 5的例子來(lái)看，1到5中，只有2,3,5是質(zhì)數(shù)，1和4不是質(zhì)數(shù)，因此排列質(zhì)數(shù)就有3*2*1 = 6種可能，分別是:

[2,3,5],[2,5,3],[3,2,5],[3,5,2],[5,2,3],[5,3,2]

不是質(zhì)數(shù)的1和4，只有兩種可能，分別是

[1,4],[4,1]

因此，將質(zhì)數(shù)和非質(zhì)數(shù)組合起來(lái)，就是6*2 = 12種可能，分別是

[1,2,3,4,5],[1,2,5,4,3],[1,3,2,4,5],[1,3,5,4,2],[1,5,2,4,3],[1,5,3,4,2]
[4,2,3,1,5],[4,2,5,1,3],[4,3,2,1,5],[4,3,5,1,2],[4,5,2,1,3],[4,5,3,1,2]

因此，我們只需要計(jì)算出n中有多少個(gè)質(zhì)數(shù)和非質(zhì)數(shù)，再計(jì)算兩者的階乘即可，為了防止溢出，題目要求我們將計(jì)算結(jié)果對(duì)1000000007取余。

public int numPrimeArrangements(int n) {
    int mod = 1000000007;
    int primeNums = countPrime(n);
    int nonPrimeNums = n - primeNums;
    long result = 1;
    for (int i=2; i<=primeNums; i++) {
        result = (result*i)%mod;
    }
    for (int j=2; j<=nonPrimeNums; j++) {
        result = (result*j)%mod;
    }
    return (int)result;
}

/**
 * 計(jì)算1到n中，質(zhì)數(shù)（只能被1和自身整除）的個(gè)數(shù)
 * @param n
 * @return
 */
public int countPrime(int n) {
    if (n <= 1) {
        return 0;
    }
    int count = 0;
    for (int i = 2; i <= n; i++) {
        boolean flag = true;
        for (int j = 2; j <= Math.sqrt(i); j++) {
            if (i % j == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            count++;
        }
    }
    return count;
}

小結(jié)

算法專題目前已更新LeetCode算法題文章270+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部?jī)?nèi)容，如果大家有什么好的解法思路、建議或者其他問(wèn)題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！