字符串组成最大的数字

回答重点

解决这个问题的核心是排序规则的选择。我们不能按照普通的字典序或者数值大小进行排序，而是需要自定义排序规则。具体来说，对于两个字符串 x 和 y，如果把它们拼接起来，A组合x+y和B组合y+x，我们需要判断哪个拼接结果更大，从而确定它们的排序顺序。

以下是 Python、Java 和 C++ 三种语言的实现：

Python 实现

▼python复制代码from functools import cmp_to_key

def largest_number(nums):

nums = sorted(nums, key=cmp_to_key(lambda x, y: int(y + x) - int(x + y)))

largest_num = ''.join(nums)

return largest_num if largest_num[0] != '0' else '0'

# 输入样例

input_data = "56 65 74 100 99 98 54"

nums = input_data.split()

result = largest_number(nums)

print(result)

Java 实现

▼java复制代码import java.util.*;

public class Main {

public static void main(String[] args) {

String input = "56 65 74 100 99 98 54";

String[] numStrings = input.split(" ");

Arrays.sort(numStrings, (a, b) -> (b + a).compareTo(a + b));

StringBuilder result = new StringBuilder();

for (String numStr : numStrings) {

result.append(numStr);

}

// Special case for leading zeros

String largestNum = result.toString();

if (largestNum.charAt(0) == '0') {

largestNum = "0";

}

System.out.println(largestNum);

}

}

C++ 实现

▼cpp复制代码#include

#include

#include

#include

using namespace std;

bool compare(const string &a, const string &b) {

return a + b > b + a;

}

string largestNumber(vector &nums) {

sort(nums.begin(), nums.end(), compare);

string result = "";

for (const string &num : nums) {

result += num;

}

if (result[0] == '0') {

return "0";

}

return result;

}

int main() {

string input = "56 65 74 100 99 98 54";

istringstream iss(input);

vector nums;

string num;

while (iss >> num) {

nums.push_back(num);

}

string result = largestNumber(nums);

cout << result << endl;

}

扩展知识

这道题主要考查排序算法和字符串处理的能力。扩展一下以下知识点：

1）自定义排序规则：我们在这个问题中使用了自定义排序规则，将两个字符串拼接后进行比较，这种方式在面试中非常常见，灵活的排序规则可以解决很多复杂问题。

2）字符串拼接与比较：通过简单的字符串操作，我们可以避免将字符串转化为整数进行比较，减少了复杂度。

3）特例处理：例如全为零的情况处理；如果组合后的数字首个字符是零，表示所有输入数字均为零，直接返回 "0" 即可。

4）语言特性：不同编程语言对排序、字符串操作有不同的库和函数，例如 Python 的 sorted 函数、Java 的 Arrays.sort 方法，以及 C++ 的 sort 函数，加深对这些常用库函数和方法的理解，可以更加高效地解决实际问题。 ...