#P3239. 最大值(200分)
-
1000ms
Tried: 114
Accepted: 41
Difficulty: 3
所属公司 :
华为od
最大值(200分)
题面描述
给定一组非负整数,重新排列它们的顺序,使得连接后的结果形成一个最大的整数。由于输出的结果可能非常大,因此需要以字符串的形式返回。
思路
要构造最大的整数,我们需要决定如何排列这些数字。关键在于比较两个数字 x 和 y 的不同排列组合 xy 和 yx,选择其中较大的一个。例如,对于 x=9 和 y=34,比较 934 和 349,显然 934 更大,因此 9 应该排在 34 的前面。
具体步骤如下:
- 读取输入并转换为字符串:将所有输入的数字转换为字符串,方便进行拼接和比较。
- 自定义排序:定义一个比较函数,比较两个字符串
a和b,通过比较ab和ba的大小来决定a和b的顺序。 - 排序数组:按照自定义的比较函数对字符串数组进行排序。
- 处理特殊情况:如果排序后的第一个数字是
0,则所有数字都是0,直接返回"0"。 - 拼接结果:将排序后的字符串数组连接起来,形成最终的最大数。
cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
// 读取输入的整数
vector<int> nums;
int num;
while(cin >> num){
nums.push_back(num);
}
// 将整数转换为字符串
vector<string> numStrs;
for(auto n : nums){
numStrs.push_back(to_string(n));
}
// 自定义排序规则
sort(numStrs.begin(), numStrs.end(), [](const string &a, const string &b) -> bool{
return a + b > b + a;
});
// 如果排序后第一个数字是0,直接输出"0"
if(numStrs.empty() || numStrs[0] == "0"){
cout << "0" << endl;
return 0;
}
// 拼接所有字符串
string result = "";
for(auto s : numStrs){
result += s;
}
cout << result << endl;
return 0;
}
python
def largest_number(nums):
# 将整数转换为字符串
num_strs = list(map(str, nums))
# 自定义排序规则
num_strs.sort(key=lambda x: x * 10, reverse=True) # 乘以 10 是为了处理长度差异
# 如果排序后第一个数字是 "0",直接返回 "0"
if num_strs[0] == "0":
return "0"
# 拼接所有字符串
return ''.join(num_strs)
if __name__ == "__main__":
# 从输入读取一行整数
nums = list(map(int, input().strip().split()))
# 输出结果
result = largest_number(nums)
print(result)
java
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取一行输入
String input = scanner.nextLine();
String[] numStrs = input.split(" ");
// 自定义排序规则
Arrays.sort(numStrs, new Comparator<String>() {
@Override
public int compare(String a, String b) {
// 比较 a+b 和 b+a 的大小
return (b + a).compareTo(a + b);
}
});
// 处理特殊情况,如果第一个数字是 "0"
if (numStrs[0].equals("0")) {
System.out.println("0");
return;
}
// 拼接所有字符串
StringBuilder result = new StringBuilder();
for (String numStr : numStrs) {
result.append(numStr);
}
// 输出结果
System.out.println(result.toString());
}
}
题目内容
给定一组整数(非负),重排顺序后输出一个最大的整数。
示例 1
输入:[10,9]
输出:910
说明:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
数组长度不超过100000
输入描述
数字组合
输出描述
最大的整数
样例1
输入
10 9
输出
910