在C++中，将给定的四个数字组成的第n个数字的位数

题目描述

给定四个数字，我们可以组成多个数字，如1234、1243、1324等等，求第n个数字的位数。

问题分析

确定n的范围

首先我们需要知道n的范围，即有多少个数字可以由给定的四个数字组成。假设四个数字分别为a、b、c、d，则可以组成的数字有4!个（全排列）。因此，如果a、b、c、d都不重复，则n的范围为1~24；如果有两个数字相等，则n的范围为1~12；如果有三个数字相等，则n的范围为1~4。如果四个数字相等，则n只能为1。

int getNum(int a, int b, int c, int d) {
    map nums;
    int arr[4] = {a, b, c, d};
    int res = 0, fac = 1;
    for(int i=3; i>=0; i--) {
        int cnt = 0;
        for(int j=0; j
            cnt += (arr[j]>arr[i]);
        }
        res += cnt * fac;
        fac *= (i+1);
    }
    return res + 1;
}

求解第n个数字

接下来，我们需要求解第n个数字。首先可以想到，将组成的数字都求出来，排序后取第n个即可。然而，由于a、b、c、d的范围都是0~9，因此可以使用循环嵌套的方式暴力枚举所有可能的组合，然后通过计数的方式找到第n个数字。

void getNums(int a, int b, int c, int d, int& cnt, string& res) {
    int arr[4] = {a, b, c, d};
    sort(arr, arr+4);
    do {
        cnt++;
        if(cnt == n) {
            res = to_string(arr[0]) + to_string(arr[1]) + to_string(arr[2]) + to_string(arr[3]);
            return;
        }
    } while(next_permutation(arr, arr+4));
}

完整代码实现

将上述代码整合起来，得到如下的完整代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int getNum(int a, int b, int c, int d) {
    map nums;
    int arr[4] = {a, b, c, d};
    int res = 0, fac = 1;
    for(int i=3; i>=0; i--) {
        int cnt = 0;
        for(int j=0; j
            cnt += (arr[j]>arr[i]);
        }
        res += cnt * fac;
        fac *= (i+1);
    }
    return res + 1;
}
void getNums(int a, int b, int c, int d, int& cnt, string& res) {
    int arr[4] = {a, b, c, d};
    sort(arr, arr+4);
    do {
        cnt++;
        if(cnt == n) {
            res = to_string(arr[0]) + to_string(arr[1]) + to_string(arr[2]) + to_string(arr[3]);
            return;
        }
    } while(next_permutation(arr, arr+4));
}
int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d >> n;
    int num = getNum(a, b, c, d);
    int cnt = 0;
    string res;
    if(num >= 1 && num <= 24) {
        for(int i=0; i<=9; i++) {
            for(int j=0; j<=9; j++) {
                if(j == i) continue;
                for(int k=0; k<=9; k++) {
                    if(k == i || k == j) continue;
                    for(int l=0; l<=9; l++) {
                        if(l == i || l == j || l == k) continue;
                        cnt++;
                        if(cnt == num) {
                            res = to_string(i) + to_string(j) + to_string(k) + to_string(l);
                            goto ANS;
                        }
                    }
                }
            }
        }
    } else if(num >= 25 && num <= 36) {
        for(int i=0; i<=9; i++) {
            for(int j=0; j<=9; j++) {
                if(j == i) continue;
                for(int k=0; k<=9; k++) {
                    if(k == i || k == j) continue;
                    cnt += (i==a) + (j==b) + (k==c);
                    if(cnt == num) {
                        res = to_string(i) + to_string(j) + to_string(k) + to_string(d);
                        goto ANS;
                    }
                    cnt += (i==a) + (j==b) + (k==d);
                    if(cnt == num) {
                        res = to_string(i) + to_string(j) + to_string(d) + to_string(c);
                        goto ANS;
                    }
                    cnt += (i==a) + (j==d) + (k==c);
                    if(cnt == num) {
                        res = to_string(i) + to_string(d) + to_string(j) + to_string(c);
                        goto ANS;
                    }
                    cnt += (i==d) + (j==b) + (k==c);
                    if(cnt == num) {
                        res = to_string(d) + to_string(j) + to_string(k) + to_string(c);
                        goto ANS;
                    }
                }
            }
        }
    } else if(num >= 37 && num <= 40) {
        for(int i=0; i<=9; i++) {
            cnt += (i==a);
            if(cnt == num) {
                res = to_string(a) + to_string(b) + to_string(c) + to_string(d);
                goto ANS;
            }
            cnt += (i==b);
            if(cnt == num) {
                res = to_string(b) + to_string(a) + to_string(c) + to_string(d);
                goto ANS;
            }
            cnt += (i==c);
            if(cnt == num) {
                res = to_string(c) + to_string(a) + to_string(b) + to_string(d);
                goto ANS;
            }
            cnt += (i==d);
            if(cnt == num) {
                res = to_string(d) + to_string(a) + to_string(b) + to_string(c);
                goto ANS;
            }
        }
    } else {
        res = to_string(a) + to_string(a) + to_string(a) + to_string(a);
    }
ANS:
    cout << res << endl;
    return 0;
}