题目
这道题目是来自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;
}
