数字排列 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

小明负责公司年会，想出一个趣味游戏:

屏幕给出 1−9 中任意 4 个不重复的数字,大家以最快时间给出这几个数字可拼成的数字从小到大排列位于第 n 位置的数字,其中 n 为给出数字中最大的(如果不到这么多数字则给出最后一个即可).

注意：

2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接，且屏幕不能同时给出 2 和 5；
6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接，且屏幕不能同时给出 6 和 9。

给出的数字：1, 4, 8, 7 则可以拼接的数字为：
1, 4, 7, 8, 14, 17, 18, 41, 47, 48, 71, 74, 78, 81, 84, 87, 147, 148, 178…（省略后面的数字）因此，第 n（即8）个数字为 41。

输入描述

输入以逗号分隔的 4 个 int 类型整数的字符串。

输出描述

输出为这几个数字可拼成的数字从小大大排列位于第 n (n为输入数字中最大的数字) 位置的数字,如果输入的数字不在范围内或者有重复，则输出 −1。

示例1

输入：
1,4,8,7

输出：
41

说明：
可以构成的数字按从小到大排序为：
1, 4, 7, 8, 14,17,18,41,47, 48, 71, 74, 78, 81, 84, 87, 147, 148,178...（省略后面的数字）故第 8 个数字为 41。

示例2

输入：
2,5,1,4

输出：
-1

说明：
2 和 5 不能同时出现。

示例3

输入：
3,0,9,1


输出：
-1


说明：
0 不在 1 到 9 的范围内。

示例4

输入：
3,9,7,8

输出：
39


说明：
注意 9 可以当 6 使用，所以可以构成的数字按从小到大排序为：
3, 6, 7, 8, 9, 36, 37, 38, 39, 63, 67, 68, 73, 76, 78, 79, 83 .... (省略后面的数字),故第9个为 39

题解

这道题目是一道组合数字的问题，需要根据给定的数字组合出所有可能的数字，然后进行排序，最后找到第n位的数字。

解题思路如下：

首先，读取输入的四个数字，构建成一个集合。
判断集合中是否有非法数字，即数字小于1或大于9的情况，以及是否同时出现了2和5、6和9。
扩展集合，将2和5等价，将6和9等价。
根据集合中的数字，生成所有可能的组合数字，包括一位数和两位数。
将生成的所有数字进行排序。
返回排序后第n位的数字。

为什么组合数字，只包括一位数和两位数？

n为输入数字中最大的数字，因此最大值是 9
输入的数字是 4 个不重复的数字，因此组成的数字个数至少为：
一位数：至少有 4 个
二位数：至少有 12 个

因此，一位和两位的组合数至少 16 个，答案拼成的数字从小大大排列位于第 n 个数肯定就包含在里面。

Java

java">import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        Set<Integer> s = new HashSet<>();
        String[] inputArr = in.nextLine().split(",");
        for (String str : inputArr) {
            s.add(Integer.parseInt(str.trim()));
        }

        int result = solve(s);
        System.out.println(result);
    }

    public static int solve(Set<Integer> s) {
        int m = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;
        for (int num : s) {
            m = Math.min(m, num); // 获取最小值
            mx = Math.max(mx, num); // 获取最大值
        }

        if (m < 1 || mx > 9) { // 存在非法的数字
            return -1;
        }

        // 不能同时出现
        if ((s.contains(2) && s.contains(5)) || (s.contains(6) && s.contains(9))) {
            return -1;
        }

        int n = mx; // n为输入数字中最大的数字

        // 为了方便组合数字，则需将可以等同的数字也加入进去
        if (s.contains(2) || s.contains(5)) {
            s.add(2);
            s.add(5);
        }
        if (s.contains(6) || s.contains(9)) {
            s.add(6);
            s.add(9);
        }

        // 拼接的数字
        Set<Integer> collect = new HashSet<>(s); // 一位数

        // 二位数的组合
        for (int x : s) {
            for (int y : s) {
                // 每个数字只能使用一次
                if (x != y && x * y != 2 * 5 && x * y != 6 * 9) {
                    collect.add(x * 10 + y);
                }
            }
        }

        // 对组成的数字排序，然后返回第 n 位的数字
        Integer[] sortedArray = collect.toArray(new Integer[0]);
        Arrays.sort(sortedArray);
        return sortedArray[n - 1];
    }
}

Python

python">
def solve(s) -> int:
    m, mx = min(s), max(s)
    if m < 1 or mx > 9:  # 存在非法的数字
        return -1

    # 不能同时出现
    if (2 in s and 5 in s) or (6 in s and 9 in s):
        return -1

    # n为输入数字中最大的数字
    n = mx

    # 为了方便组合数字，则需将可以等同的数字也加入进去
    if (2 in s or 5 in s):
        s.add(2)
        s.add(5)
    if (6 in s or 9 in s):
        s.add(6)
        s.add(9)

    # 拼接的数字
    collect = set(s)  # 一位数

    # 二位数的组合
    for x in s:
        for y in s:
            # 每个数字只能使用一次
            if x != y and x * y != 2 * 5 and x * y != 6 * 9:
                collect.add(x * 10 + y)

    # 对组成的数字排序，然后返回第 n 位的数字
    sorted_array = sorted(list(collect))
    return sorted_array[n - 1]


if __name__ == "__main__":
    arr = set(map(int, input().split(",")))
    print(solve(arr))

C++

#include <bits/stdc++.h>
using namespace std;

int solve(set<int>& s)
{

    int m = *s.begin(), mx = *(--s.end());
    if (m < 1 || mx > 9) {   // 存在非法的数字
        return -1;
    }

    // 不能同时出现
    if ((s.find(2) != s.end() && s.find(5) != s.end()) || (s.find(6) != s.end() && s.find(9) != s.end())) {
        return -1;
    }

    int n = mx;   // n为输入数字中最大的数字

    // 为了方便组合数字，则需将可以等同的数字也加入进去
    if (s.find(2) != s.end() || s.find(5) != s.end()) {
        s.insert(2);
        s.insert(5);
    }
    if (s.find(6) != s.end() || s.find(9) != s.end()) {
        s.insert(6);
        s.insert(9);
    }

    // 拼接的数字
    set<int> collect(s);   // 一位数

    // 二位数的组合
    for (auto x : s) {
        for (auto y : s) {
            // 每个数字只能使用一次
            if (x != y && x * y != 2 * 5 && x * y != 6 * 9) {
                collect.insert(x * 10 + y);
            }
        }
    }

    // 对组成的数字排序，然后返回第 n 位的数字
    vector<int> sorted_array(collect.begin(), collect.end());
    sort(sorted_array.begin(), sorted_array.end());
    return sorted_array[n - 1];
}

int main()
{
    set<int> s;
    for (int i = 0, x; i < 4; i++) {
        cin >> x;
        s.insert(x);
        if (cin.peek() == ',') cin.ignore();
    }
    cout << solve(s) << endl;
    return 0;
}