华为OD机试E卷 ---最大值

一、题目描述

给定一组整数(非负)，重排顺序后输出一个最大的整数。

二、示例1

用例1

输入

10 9

输出

910

说明:输出结果可能非常大，所以你需要返回一个 字符串只而不是整数。

三、输入描述

数字组合

四、输出描述

最大的整数

五、解题思路

1. 字符串转换：

   • 首先，将整数数组中的每个元素转换为字符串，以便进行字符串比较和拼接。

2. 自定义排序：

   • 使用自定义的比较器对字符串数组进行排序。比较规则是：对于任意两个字符串a和b，比较a + b和b + a的大小。
   • 如果a + b大于b + a，则a应该排在b前面，以形成更大的数字。
   • 反之，如果a + b小于b + a，则b应该排在a前面。
   • 如果两者相等，则保持相对顺序不变（或者可以根据具体实现选择任意一种顺序，因为不影响最终结果）。

3. 处理特殊情况：

   • 排序后，如果数组的第一个元素是"0"，则需要检查数组中是否全部为"0"。
   • 如果全部为"0"，则直接返回"0"。
   • 如果不是全部为"0"，但由于某些数字（如0）的存在，在排序后可能导致结果不是以最大数字开头（尽管这种情况在题目给定的非负整数范围内不太可能，但作为一种健壮性考虑），仍然需要按照排序后的结果拼接。
   • 实际上，在题目给定的非负整数范围内，只要正确实现了自定义排序，就不会出现以非最大数字开头的情况。

4. 拼接结果：

   • 将排序后的字符串数组使用StringBuilder或简单的字符串拼接操作合并成一个结果字符串。

5. 返回结果：

   • 返回拼接后的结果字符串作为最终输出。

六、代码实现(python)

from functools import cmp_to_key


def largest_number(nums):
    # 自定义比较函数，用于确定两个数字拼接后的顺序
    def compare(x, y):
        # 将数字转换为字符串，并比较它们拼接后的结果
        xy = str(x) + str(y)
        yx = str(y) + str(x)
        # 根据拼接后的字符串比较大小
        if xy > yx:
            return -1  # x应该排在y前面
        elif xy < yx:
            return 1  # y应该排在x前面
        else:
            return 0  # x和y拼接后的结果相等

    # 将数字列表转换为字符串列表，以便排序
    nums_str = list(map(str, nums))

    # 使用自定义的比较函数对字符串列表进行排序
    nums_str.sort(key=cmp_to_key(compare))

    # 将排序后的字符串列表拼接成一个字符串
    result = ''.join(nums_str)

    # 处理特殊情况：如果结果字符串以'0'开头（且不是整个字符串都是'0'），则去掉前面的'0'
    # 如果结果字符串全是'0'，则返回'0'
    if result[0] == '0':
        return '0'

    # 返回最终结果
    return result


def main():
    # 从用户获取输入
    input_str = input("请输入一组数字，用逗号分隔: ").strip()

    # 将输入字符串转换为整数列表
    try:
        nums = list(map(int, input_str.split(',')))
    except ValueError:
        print("输入格式错误，请输入一组用逗号分隔的数字。")
        return

    # 调用 largest_number 函数并输出结果
    result = largest_number(nums)
    print("最大拼接数字:", result)


# 确保 main 方法只在直接运行脚本时执行
if __name__ == "__main__":
    main()

# 测试用例
# print(largest_number([10, 9]))  # 输出 "910"
# print(largest_number([3, 30, 34, 5, 9]))  # 输出 "9534330"
# print(largest_number([1, 2, 3, 4, 5, 6, 7, 8, 9]))  # 输出 "987654321"
# print(largest_number([0, 0]))  # 输出 "0"
# print(largest_number([0, 0, 1]))  # 输出 "100"

七、代码实现(java)

import java.util.Arrays;
import java.util.Comparator;

public class LargestNumber {
    /**
     * 将一组整数重排顺序后输出一个最大的整数
     *
     * @param nums 包含非负整数的数组
     * @return 由这些整数组成的最大数字的字符串表示
     */
    public static String largestNumber(int[] nums) {
        // 将整数数组转换为字符串数组
        String[] numStrs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numStrs[i] = String.valueOf(nums[i]);
        }

        // 自定义排序规则：比较两个字符串拼接的两种顺序，决定哪个顺序更大
        Arrays.sort(numStrs, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                String order1 = a + b;
                String order2 = b + a;
                return order2.compareTo(order1); // 降序排列
            }
        });

        // 如果排序后的第一个元素是"0"，说明所有元素都是0，直接返回"0"
        if (numStrs[0].equals("0")) {
            return "0";
        }

        // 将排序后的字符串数组拼接成结果字符串
        StringBuilder largestNumber = new StringBuilder();
        for (String numStr : numStrs) {
            largestNumber.append(numStr);
        }

        return largestNumber.toString();
    }

    public static void main(String[] args) {
        int[] nums = {10, 9};
        System.out.println(largestNumber(nums)); // 输出: 910
    }
}

八、运行示例解析

测试用例

public static void main(String[] args) {
    int[] nums = {10, 9};
    System.out.println(largestNumber(nums)); // 输出: 910
}

解析步骤

1. 初始化数组:

   • 输入数组nums为{10, 9}。

2. 转换为字符串数组:

   • 方法内部，首先将整数数组转换为字符串数组numStrs，得到{"10", "9"}。

3. 自定义排序:

   • 使用Arrays.sort方法和自定义的Comparator对字符串数组进行排序。
   • 比较规则是：将两个字符串a和b分别进行拼接，形成a + b和b + a，然后比较这两个拼接字符串的大小。
   • 在本例中，比较"10" + "9"和"9" + "10"，即"109"和"910"。
   • 由于"910"大于"109"，因此自定义比较器会判定"9"应该排在"10"前面。
   • 排序后，numStrs变为{"9", "10"}（但实际上，由于我们的比较规则是降序排列以形成最大数，排序后的结果应该直接满足这个顺序，这里的描述是为了说明比较过程）。

4. 处理特殊情况:

   • 检查排序后的数组的第一个元素是否为"0"。如果是，且数组中只包含零（虽然在这个特定例子中不是这种情况），则直接返回"0"。
   • 在本例中，numStrs[0]是"9"，不是"0"，因此不需要特殊处理。

5. 拼接结果字符串:

   • 使用StringBuilder将排序后的字符串数组拼接成一个结果字符串。
   • 在本例中，拼接后的结果是"910"。

6. 返回结果:

   • 方法返回拼接后的结果字符串"910"。

7. 打印输出:

   • 在main方法中，打印调用largestNumber(nums)的返回值，输出为"910"。

九、注意事项

• 在自定义排序中，比较器返回的是order2.compareTo(order1)，这是因为我们想要实现的是降序排列以形成最大数。如果order2大于order1，则compare方法应该返回正数，表示b应该排在a前面（但在数组中实际上是a排在b的位置被交换到了后面，因为Arrays.sort默认是升序排序，我们通过返回负数的相反数来实现降序）。
• 在处理特殊情况时，由于题目要求非负整数，因此如果排序后的第一个元素是"0"，则可以直接返回"0"，无需进一步检查数组中是否包含其他非零元素（因为如果有其他非零元素，它们会在排序过程中被正确地放在"0"的前面）。但作为一种健壮性考虑，上述代码仍然检查了排序后的第一个元素是否为"0"，并相应地返回了结果。在实际应用中，这种检查可能是多余的，具体取决于题目的严格要求和输入数据的范围。