程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Permutation Sequence

leetcode筆記:Permutation Sequence

編輯:關於C++

一.題目描述

這裡寫圖片描述

題目的意思是,假設有{1,2,3,4,…,n},對其中的元素進行排列,總共有n!種組合,將它們從小到大排序,問其中第k個組合的形式是怎樣的?<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+tv4uzOLEv7fWzvY8L3N0cm9uZz48L3A+DQo8cD48c3Ryb25nPre9t6jSuzwvc3Ryb25nPqO6v8nS1NK7uPbSu7j2tcSwtLTO0PKxqcGmx/O94qGjvt/M5cq1z9a/ybLO1dXM4sS/o7pOZXh0IFBlcm11dGF0aW9uoaPV4sDvsqLDu9PQyrXP1qOs1vfSqtHQvr+1xMrHt723qLb+tcRDYW50b3IgZXhwYW5zaW9uy+O3qKGjPC9wPg0KPHA+PHN0cm9uZz63vbeotv48L3N0cm9uZz6jusr90ae94reoo7pDYW50b3IgZXhwYW5zaW9uPC9wPg0KPHA+Q2FudG9yIGV4cGFuc2lvbsvjt6i1xMu8z+vKx6Os1No8Y29kZT5uITwvY29kZT649sXFwdDW0KOstdrSu867tcTUqsvY19zKxzxjb2RlPihuLTEpITwvY29kZT7Su9fps/bP1rXEo6zSsr7Ny7XI57n7PGNvZGU+cCA9IGsgLyAobi0xKSE8L2NvZGU+o6zEx8O0xcXB0LXE1+6/qsq80ru49tSqy9jSu7aoysc8Y29kZT5udW1zW3BdPC9jb2RlPqGj0tTPwrmryr24+LP2wcvIq8XFwdC1vdK7uPbX1Mi7yv21xNK70rvLq8nko7o8L3A+DQo8cHJlIGNsYXNzPQ=="brush:java;"> X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!

舉個例子:

1324{1,2,3,4}排列數中第幾個組合:

第一位是1,小於1的數沒有,是0個,0*3!,第二位是3,小於3的數有12,但1已經存在於第一位了,所以只有一個數21*2! 。第三位是2小於2的數是1,但1在第一位,所以有0個數,0*1!,所以比1324小的排列有0*3!+1*2!+0*1!=2個,1324是第3個組合。

以上是Cantor編碼的過程,即把一個全排列映射1324為一個自然數3,而該題目是已知一個自然數k,求其對應的全排列,相對以上步驟來說是一個解碼的過程,下面給出一個具體的例子:

如何找出{1,2,3,4,5}的第16個排列?
1. 首先用16-1,得到15
2. 用15去除4! ,得到0,余15
3. 用15去除3! ,得到2,余3
4. 用3去除2! ,得到1,余1
5. 用1去除1! ,得到1,余0
6. 有0個數比它小的數是1,所以第一位是1
7. 有2個數比它小的數是3,但1已經在之前出現過,所以第二位是4
8. 有1個數比它小的數是2,但1已經在之前出現過了所以第三位是3
9. 有1個數比它小的數是2,但1,3,4都出現過了所以第四位是5
10. 根據上述推論,最後一個數只能是2

所以排列為{1,4,3,5,2}

按照以上思路,可以開始設計算法。

三.示例代碼

#include 
#include 
#include 
using namespace std;

class Solution
{
public:
    string PermutationSequence(int n, int k)
    {
        int total = CombinedNumber(n - 1);
        if (k > total)
        {
            cout << The k is larger then the total number of permutation sequence: << total << endl;
            return Null!;
        }

        string a(n, '0');
        for (int i = 0; i < n; ++i)
            a[i] += i + 1;   // sorted

        // Cantor expansion
        string s = a, result;
        k--; // (k - 1) values are less than the target value 

        for (int i = n - 1; i > 0; --i)
        {
            auto ptr = next(s.begin(), k / total);
            result.push_back(*ptr);
            s.erase(ptr);  // delete the already used number
            k %= total;    // update the dividend
            total /= i;    // update the divider
        }
        result.push_back(s[0]);  // The last bit
        return result;
    }

private:
    int CombinedNumber(int n)
    {
        int num = 1;
        for (int i = 1; i < n + 1; ++i)
            num *= i;
        return num;
    }
};

以下是簡易的測試代碼:

#include PermutationSequence.h

int main()
{
    Solution s;

    int n = 6, k = 150;
    string result = s.PermutationSequence(n, k);

    std::cout << n =  << n <<  and the  << k << th sequence is:  << result << std::endl;

    getchar();

    return 0;
}

一個正確的測試結果,n = 6k = 16

這裡寫圖片描述

k的取值超過可能的組合數量時:

這裡寫圖片描述

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved