1403: 【基础】整数的拼接-2

Question

1403: 【基础】整数的拼接-2
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：外部导入
提交：18
解决：10
题目描述
设有n个整数(3≤n≤100)，将这些整数拼接起来，可以形成一个最大的整数。
例如：n=3，三个整数分别为21 7 34， 拼接后最大的整数为： 73421
再比如：n=3，三个整数分别是1 10 110，拼接后最大的整数是：111010
输入
第一行一个整数n ，表示有n 个整数。
第二行n个整数，数与数之间用一个空格分隔。
输出
输出到屏幕 。一个拼接后的最大的整数。
样例输入 复制
3
21 7 34
样例输出 复制
73421

Answer 1

思路：
首先，将输入的整数转换为字符串类型，然后将字符串数组按特定规则进行排序，最后将排序后的字符串数组进行拼接输出。

具体步骤如下：

1. 读取输入的整数n，并创建一个长度为n的字符串数组nums。
2. 读取输入的n个整数，将其转换为字符串并存储到nums中。
3. 使用冒泡排序算法对字符串数组nums进行排序。排序规则为，比较两个字符串 x 和 y，如果 x+y>y+x，则将 x 排在 y 前面。
4. 将排序后的字符串数组nums进行拼接，并输出结果。

代码实现如下：

n = int(input())
nums = input().split()

# 冒泡排序
for i in range(n-1):
    for j in range(n-i-1):
        if nums[j] + nums[j+1] < nums[j+1] + nums[j]:
            nums[j], nums[j+1] = nums[j+1], nums[j]

# 拼接并输出结果
result = ''.join(nums)
print(result)

复杂度分析：
时间复杂度：冒泡排序的时间复杂度为 O(n^2)，拼接字符串的时间复杂度为 O(n)，总体时间复杂度为 O(n^2)。
空间复杂度：创建了一个长度为n的字符串数组，空间复杂度为 O(n)。