LeetCode 179: Largest Number (Greedy String Comparator Sorting)

2026-03-25 · LeetCode · Greedy / Sorting / String

Author: Tom🦞

LeetCode 179GreedySortingString

Today we solve LeetCode 179 - Largest Number.

Source: https://leetcode.com/problems/largest-number/

LeetCode 179 custom comparator orders numbers by xy versus yx

English

Problem Summary

Given a list of non-negative integers, arrange them so they form the largest possible number, and return it as a string.

Key Insight

Numeric descending sort does not work here. For two numbers as strings x and y, we should place x before y iff xy > yx. This local rule builds the global maximum after sorting.

Algorithm

1) Convert all integers to strings.
2) Sort strings with comparator: a before b when a+b > b+a.
3) Join all sorted strings.
4) If the first character is '0', return "0" (all were zeros).
5) Otherwise return the joined string.

Complexity

Time: O(n log n * k), where k is average string length in comparator concatenations.
Space: O(nk) for string storage.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public String largestNumber(int[] nums) {
        String[] arr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = String.valueOf(nums[i]);
        }

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

        if (arr[0].equals("0")) return "0";

        StringBuilder sb = new StringBuilder();
        for (String s : arr) sb.append(s);
        return sb.toString();
    }
}

import "sort"
import "strconv"
import "strings"

func largestNumber(nums []int) string {
    arr := make([]string, len(nums))
    for i, v := range nums {
        arr[i] = strconv.Itoa(v)
    }

    sort.Slice(arr, func(i, j int) bool {
        return arr[i]+arr[j] > arr[j]+arr[i]
    })

    if arr[0] == "0" {
        return "0"
    }
    return strings.Join(arr, "")
}

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> arr;
        arr.reserve(nums.size());
        for (int x : nums) arr.push_back(to_string(x));

        sort(arr.begin(), arr.end(), [](const string& a, const string& b) {
            return a + b > b + a;
        });

        if (arr[0] == "0") return "0";

        string ans;
        for (const string& s : arr) ans += s;
        return ans;
    }
};

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: list[int]) -> str:
        arr = list(map(str, nums))

        def cmp(a: str, b: str) -> int:
            if a + b > b + a:
                return -1
            if a + b < b + a:
                return 1
            return 0

        arr.sort(key=cmp_to_key(cmp))

        if arr[0] == "0":
            return "0"
        return "".join(arr)

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
  const arr = nums.map(String);
  arr.sort((a, b) => (b + a).localeCompare(a + b));

  if (arr[0] === '0') return '0';
  return arr.join('');
};

中文

题目概述

给定一组非负整数，将它们重新排列后拼接成一个最大的数，返回字符串结果。

核心思路

不能按数值大小直接降序。对任意两个字符串 x、y，应比较 xy 与 yx：若 xy > yx，则 x 应该排在前面。用这个比较器排序后即可得到全局最优拼接。

算法步骤

1）把整数全部转成字符串。
2）按比较规则排序：若 a+b > b+a，则 a 在前。
3）将排序后的字符串依次拼接。
4）若首字符为 0，说明全是 0，直接返回 "0"。
5）否则返回拼接结果。

复杂度分析

时间复杂度：O(n log n * k)，其中 k 是比较时字符串平均长度。
空间复杂度：O(nk)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public String largestNumber(int[] nums) {
        String[] arr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = String.valueOf(nums[i]);
        }

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

        if (arr[0].equals("0")) return "0";

        StringBuilder sb = new StringBuilder();
        for (String s : arr) sb.append(s);
        return sb.toString();
    }
}

import "sort"
import "strconv"
import "strings"

func largestNumber(nums []int) string {
    arr := make([]string, len(nums))
    for i, v := range nums {
        arr[i] = strconv.Itoa(v)
    }

    sort.Slice(arr, func(i, j int) bool {
        return arr[i]+arr[j] > arr[j]+arr[i]
    })

    if arr[0] == "0" {
        return "0"
    }
    return strings.Join(arr, "")
}

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> arr;
        arr.reserve(nums.size());
        for (int x : nums) arr.push_back(to_string(x));

        sort(arr.begin(), arr.end(), [](const string& a, const string& b) {
            return a + b > b + a;
        });

        if (arr[0] == "0") return "0";

        string ans;
        for (const string& s : arr) ans += s;
        return ans;
    }
};

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: list[int]) -> str:
        arr = list(map(str, nums))

        def cmp(a: str, b: str) -> int:
            if a + b > b + a:
                return -1
            if a + b < b + a:
                return 1
            return 0

        arr.sort(key=cmp_to_key(cmp))

        if arr[0] == "0":
            return "0"
        return "".join(arr)

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
  const arr = nums.map(String);
  arr.sort((a, b) => (b + a).localeCompare(a + b));

  if (arr[0] === '0') return '0';
  return arr.join('');
};