How does greedy strategy help solve the Largest Number problem?

Greedy strategy helps by ensuring that numbers are ordered in a way that maximizes the concatenated result. The custom sorting based on concatenated strings guarantees the largest number formation.

What is the time complexity of the solution?

The time complexity of the solution is O(n log n) due to the sorting step where n is the number of elements in the list.

How do we handle cases where all numbers are zero?

If all numbers are zero, the result should be '0' to avoid an invalid output like '000'. This is checked after sorting.

Can we use other sorting algorithms for this problem?

While other sorting algorithms could be used, the key is using a custom comparator to ensure correct order based on concatenation. A heap or bucket sort could be used in certain cases.

What happens if we return an integer instead of a string?

Returning an integer instead of a string will cause issues with large numbers that exceed integer limits. The problem explicitly requires the result to be a string.

#179

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

最大数

给定一组非负整数 nums ，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。示例 1：输入： nums = [10,2] 输出： "210" 示例 2：输入： nums = [3,30,34,5,9] 输出：…

数组字符串贪心排序

题目描述

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

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

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：自定义排序

先转成字符串列表，再对字符串列表进行字典序降序排列。最后将列表所有字符串拼接即可。

1

2

3

4

5

6

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(v) for v in nums]
        nums.sort(key=cmp_to_key(lambda a, b: 1 if a + b < b + a else -1))
        return "0" if nums[0] == "0" else "".join(nums)

speed

复杂度分析

指标	值
时间	O(n \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently explain why sorting is key in forming the largest number?
question_mark
Does the candidate address edge cases such as leading zeros or large number sizes?
question_mark
How well does the candidate handle performance considerations when discussing sorting and comparisons?

warning

常见陷阱

外企场景

error
Overlooking the need for a custom sorting function for concatenation comparisons.
error
Failing to handle edge cases, especially when all elements are zeros or very large numbers.
error
Returning an integer instead of a string when the output can be very large.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Use a different sorting method such as a priority queue or bucket sort to optimize performance.
arrow_right_alt
Consider a variation where you need to handle both positive and negative numbers in the input.
arrow_right_alt
Solve the problem while restricting to a certain time complexity or memory limit.

help

常见问题

外企场景

继续练习

#49 字母异位词分组 #324 摆动排序 II #435 无重叠区间