179. 最大数

🟠   🔖  贪心 数组 字符串 排序  🔗 力扣 LeetCode

题目

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]

Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]

Output: "9534330"

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

题目大意

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

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

示例 1：

**输入：**nums = [10,2]

输出："210"

示例 2：

**输入：**nums = [3,30,34,5,9]

输出："9534330"

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

解题思路

1. 将数字转换为字符串：

   • 直接对数字排序无法满足题目要求，因为数字的连接顺序会影响结果。
   • 需要将数组中的数字转换为字符串，以便按自定义规则排序。

2. 定义排序规则：

   • 对于两个字符串 a 和 b：
     • 如果 b + a 的数值大于 a + b，说明 b 应排在 a 前面。
     • 按此规则进行降序排序。

3. 处理特殊情况：

   • 如果排序后数组的第一个元素是 "0"，说明所有数字都是 0，直接返回 "0"。

4. 拼接结果：

   • 排序完成后，将数组中的字符串连接成结果字符串。

复杂度分析

• 时间复杂度：O(k * n log n)

  • 排序复杂度为 O(n log n)，其中 n 是数组长度。
  • 排序过程中比较两个字符串的复杂度与其长度有关，假设平均字符串长度为 k，每次比较需要 O(k) 时间。
  • 总时间复杂度为 O(k * n log n)。

• 空间复杂度：O(n * k)，转换为字符串的数组占用 O(n * k) 空间，k 是字符串的平均长度。

代码

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function (nums) {
	// 将数字转换为字符串
	let arr = nums.map(String);

	// 自定义排序规则
	arr.sort((a, b) => Number(b + a) - Number(a + b));

	// 如果最大的数字是 "0"，说明所有数字都是 "0"
	if (arr[0] === '0') return '0';

	// 拼接排序后的字符串
	return arr.join('');
};

相关题目

题号	标题	题解	标签	难度	力扣
2165	重排数字的最小值		数学 排序	🟠	🀄️ 🔗
3270	求出数字答案		数学	🟢	🀄️ 🔗