題目

這道題目是來自leetcode的，第60題：題目的網(wǎng)址

題目的截圖

思路

這道題目意思是輸入一個(gè)n，1-n任意順序呢可以組成一個(gè)數(shù)，從小到大排序這些數(shù)，找到第k個(gè)大小的數(shù)。

這題我拿到手先搞了個(gè)遞歸的方法，就是把所有的數(shù)都求出來，選第k個(gè)，超時(shí)了絕大多數(shù)的案例，然后我優(yōu)化了一下遞歸，在取到第k個(gè)值的時(shí)候返回，多通過了一些測(cè)試案例。感覺遞歸這條路走不下去了。后來我看了一篇CSDN的博客，博客講的是康拓編碼，感覺很高端，我大致知道個(gè)思路，準(zhǔn)備自己寫，我覺得用set更加好，set不會(huì)存放重復(fù)的數(shù)據(jù)，而且還可以erase掉指定的value，還可以排序，這個(gè)很重要。下面就介紹一下這題最終的思路。

首先將初始化一個(gè)棧，將0 - n-1的階乘放入棧中，然后初始化一個(gè)set，將1-n放入set中，初始化完畢以后，你就可以大展身手啦，每次從棧中彈出一個(gè)階乘，這個(gè)階乘一定是n-1位的所有的可能性的值的個(gè)數(shù)。如下圖，n = 4，3! 為6，那么我們現(xiàn)在用k/6得到的一定是第幾個(gè)大組，這里k是9，這里需要k--，方便計(jì)算求余。8 / 6為1，相當(dāng)于第二組，那么就是從我們的set中將第二個(gè)取出來，取出的是2，將set中的2 erase掉，重新自動(dòng)排序，重復(fù)剛剛的過程。每次取出的值就是set中的第幾個(gè)。逐個(gè)除以并且求余。最后一個(gè)直接加入。

樣例截圖

代碼

//
//  main.cpp
//  leetcode60
//
//  Created by 李林 on 2017/1/13.
//  Copyright ? 2017年 lee. All rights reserved.
//

#include <iostream>
#include <string>
#include <set>
#include <stack>
using namespace std;

class Solution {
public:
    stack<int> initStack(int n){
        int sum = 1;
        stack<int> st;
        
        for(int i=1; i<n; i++){
            sum = sum * i;
            st.push(sum);
        }
        
        return st;
    }
    
    string getPermutation(int n, int k) {
        string result;
        set<int> nums;
        stack<int> st;
        if(k == 0)  return result;
        
        // 1.初始化
        for(int i=1; i<=n; i++)
            nums.insert(i);
        st = initStack(n);
        
        // 2.計(jì)算
        k--;
        while(!st.empty()) {
            int index = k / st.top();
            k %= st.top();
            
            // 2.1取值
            int count = -1;
            for(set<int>::iterator it = nums.begin(); it!=nums.end(); it++){
                count++;
                if(index == count){
                    result.push_back('0' + (*it));
                    nums.erase(*it);
                    break;
                }
            }

            st.pop();
        }
        
        result.push_back('0' + (*nums.begin()));
        
        return result;
    }
};

int main(int argc, const char * argv[]) {
    Solution s;
    
    string result = s.getPermutation(4, 9);
    cout<<result<<endl;
    
    return 0;
}