尽管标题表明您正在寻找一种将十进制数转换为整数的方法，但我将给出您要解决的实际问题的答案：如何获得 N 元素数组的第 K 次排列。
简而言之，您需要逐位预测给定数组的第 K 个排列。事物的理论方面非常简单。假设您在数组 A 中有元素，并且存储了有关每个元素是否在第二个数组 S 中使用的信息。当您为每个数字选择适当的值时，S 将被更新。结果将存储在数组 R 中。
有N个！给定数组 A 中元素的排列。对于具有 N 个数字的数组，让我们考虑如果 A 中的最小元素被选为结果中最左边的数字，则有多少个排列，R[0]。是（N-1）！对吧？所以从 #1 到 #(N-1) 的排列！属于结果的最左边元素是 A 中最小元素的情况。排列 #((N-1)! + 1) 到 #(2 *(N-1)!) 具有 A 的第二最小值作为 R [0]。所以排列 #((i-1) * (N-1)! + 1) 到 #(i * (N-1)!) 使用 A 中第 i 个未使用且按字典顺序最小的数字作为 R[0]。
在更广义的意义上，在 R[d] 中使用的值是第 K 个字典序最小排列是 A[i] 使得 A[i] 是迄今为止未使用的第 i 个字典序最小元素并且使得 (i * (N-1-d)! + 1) <= k和k <= ((i+1) * (N-1-d)!)。
如果您遍历整个 S ，将需要O(N)时间来找到合适的 i 值。我不确定您如何准确地实现它，但您也可以对 S 进行二进制搜索并找到合适的我在 O(logN) 时间内。
如果您有较大的 K 值，我认为您将需要实现大整数乘法才能进行比较，但如果我想出一个聪明的方法来解决这个问题，我会更新这部分答案。
一旦你选择了正确的 i，你就可以将 A[i] 分配为 R[d] 并继续寻找下一个数字。
下面是实现此解决方案的一段代码。它很长，但大部分只是大整数实现。该算法的要点实际上不到 30 行。我只是想提供一个工作代码，以便您可以根据需要自行测试。
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define NLIMIT 100
#define ASIZELIMIT 101
#define BIGINTBUCKETSLIMIT 100
#define BUCKETCAPACITY 1000000000
#define DIGITSPERBUCKET 9
using namespace std;
/* sufficient big integer implementation */
class BigInt
{
/*
* Note that BIGINTBUCKETSLIMIT should be high enough so that
* the values given as input does not cause overflow
* or access violation from the last bucket in operations
* multiply and subtract.
*/
public:
long long buckets[BIGINTBUCKETSLIMIT];
BigInt() {
for(int i=0; i < BIGINTBUCKETSLIMIT; ++i) {
buckets[i] = 0LL;
}
}
BigInt(int initialValue) {
for(int i=0; i < BIGINTBUCKETSLIMIT; ++i)
{
buckets[i] = initialValue % BUCKETCAPACITY;
initialValue /= BUCKETCAPACITY;
}
}
void multiply(int val) {
for(int i= BIGINTBUCKETSLIMIT - 1; i >= 0; --i)
buckets[i] = buckets[i] * val;
for(int i=0; i < BIGINTBUCKETSLIMIT - 1; ++i) {
buckets[i+1] += buckets[i] / BUCKETCAPACITY;
buckets[i] = buckets[i] % BUCKETCAPACITY;
}
}
void subtract(BigInt B) {
for(int i= 0; i < BIGINTBUCKETSLIMIT; ++i) {
buckets[i] = buckets[i] - B.buckets[i];
if(buckets[i] < 0LL) {
buckets[i] += BUCKETCAPACITY;
buckets[i+1]--;
}
}
}
const BigInt & operator=(const BigInt &B) {
for(int i=0; i < BIGINTBUCKETSLIMIT; ++i)
buckets[i] = B.buckets[i];
return *this;
}
bool operator<(const BigInt &B) {
for(int i=BIGINTBUCKETSLIMIT-1; i >= 0; --i)
if(buckets[i] != B.buckets[i])
return buckets[i] < B.buckets[i];
return false;
}
void importFromStr(string &src)
{
long long buffer = 0, j = 0;
for(int i=src.size() - 1; i >= 0; i -= DIGITSPERBUCKET) {
buffer = 0;
for(int k=max(0, i - DIGITSPERBUCKET + 1); k <= i; ++k) {
buffer = buffer * 10 + (src[k] - '0');
}
buckets[j++] = buffer;
}
}
};
BigInt factorials[ASIZELIMIT];
void preprocessFactorials(int n)
{
factorials[0] = BigInt(1);
for(int i=1; i <= n; ++i) {
factorials[i] = factorials[i-1];
factorials[i].multiply(i);
}
}
void findKthPermutation(int N, int A[], BigInt K, int result[]) {
BigInt tmpBigInt;
bool S[ASIZELIMIT];
for(int i=0; i < N; ++i)
S[i] = true;
K.subtract(BigInt(1));
preprocessFactorials(N);
for(int d=0; d < N; ++d) {
for(int i=0, j=0; i < N; ++i) {
if(S[i]) {
tmpBigInt = factorials[N-1-d];
tmpBigInt.multiply(j+1);
if(K < tmpBigInt) {
result[d] = A[i];
S[i] = 0;
tmpBigInt = factorials[N-1-d];
tmpBigInt.multiply(j);
K.subtract(tmpBigInt);
break;
}
++j;
}
}
}
}
int main() {
string k;
BigInt K;
int N;
int A[ASIZELIMIT], R[ASIZELIMIT];
cin >> N >> k;
for(int i=0; i < N; ++i)
cin >> A[i];
K.importFromStr(k);
sort(A, A+N);
findKthPermutation(N, A, K, R);
cout << R[0];
for(int i=1; i < N; ++i)
cout << " " << R[i];
cout << endl;
return 0;
}
您可能很容易观察到函数 findKthPermutation 和我的 BigInt 类中的 2 个循环，无论 K 是多少，该实现都在 O(N 3 ) 中工作。虽然我不知道您的确切性能需求，因为 N <= 100，它可能是足够高效。如果它没有您希望的那么有效，我的第一个建议是使用其他数据结构优化将信息存储在 S 中，这些数据结构可能会在 O(logN) 时间内产生为每个数字 d 寻找的适当 i 值。
最后，请注意，此解决方案假定 A 不包含重复元素，因为这会干扰可能排列的字典枚举。