题目

这道题目是来自leetcode的，第60题：题目的网址

题目的截图

思路

这道题目意思是输入一个n，1-n任意顺序呢可以组成一个数，从小到大排序这些数，找到第k个大小的数。

这题我拿到手先搞了个递归的方法，就是把所有的数都求出来，选第k个，超时了绝大多数的案例，然后我优化了一下递归，在取到第k个值的时候返回，多通过了一些测试案例。感觉递归这条路走不下去了。后来我看了一篇CSDN的博客，博客讲的是康拓编码，感觉很高端，我大致知道个思路，准备自己写，我觉得用set更加好，set不会存放重复的数据，而且还可以erase掉指定的value，还可以排序，这个很重要。下面就介绍一下这题最终的思路。

首先将初始化一个栈，将0 - n-1的阶乘放入栈中，然后初始化一个set，将1-n放入set中，初始化完毕以后，你就可以大展身手啦，每次从栈中弹出一个阶乘，这个阶乘一定是n-1位的所有的可能性的值的个数。如下图，n = 4，3! 为6，那么我们现在用k/6得到的一定是第几个大组，这里k是9，这里需要k--，方便计算求余。8 / 6为1，相当于第二组，那么就是从我们的set中将第二个取出来，取出的是2，将set中的2 erase掉，重新自动排序，重复刚刚的过程。每次取出的值就是set中的第几个。逐个除以并且求余。最后一个直接加入。

样例截图

代码

//
//  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.计算
        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;
}